Count Lattice Points Inside A Circle - Leetcode Solution

Problem Statement:

Given the coordinates (x, y) of a center and the radius r of a circle, find the number of lattice points (integer coordinates on a plane) inside the circle, including on the circumference.

Example:

Input: Center = (0,0), Radius = 2

Output: 5

Explanation: There are 5 lattice points within the circle with radius 2 and center at (0,0), they are: (0,0), (1,1), (1,-1), (-1,1), (-1,-1)

Solution:

To solve this problem, we need to find the lattice points inside the circle. A lattice point is defined by a pair of integer coordinates on a plane, and it is on the circumference of the circle if it satisfies the equation x^2 + y^2 = r^2.

We can start by iterating through all possible x and y integer coordinates within the range of the circle. For each coordinate (x,y), we check if it is inside or on the circumference of the circle by comparing it with the equation of the circle.

The equation for each point (x,y) is x^2 + y^2 <= r^2. If this condition is satisfied, we have found a lattice point inside the circle, and we count it.

To iterate through all possible x and y integer coordinates within the range of the circle, we need to determine the bounds for x and y. We can bound x and y to a range of [-r, r], since any point outside this range would certainly be outside the circle.

Therefore, our algorithm can be summarized as follows:

1. Initialize a counter variable count to 0.
2. Iterate through all possible integer coordinates (x,y) within the range [-r, r].
3. For each coordinate (x,y), check if it is inside or on the circumference of the circle by comparing it with the equation x^2 + y^2 <= r^2.
4. If the condition is satisfied, increment the count by one.
5. Return the count as the result.

Pseudo Code:

count = 0 for x in range(-r, r+1): for y in range(-r, r+1): if xx + yy <= r*r: count += 1 return count

Time Complexity: O(r^2)

The time complexity of this algorithm is O(r^2), since we need to iterate through all possible integer coordinates within the range [-r, r], which contains O(r^2) points. The computation for xx + yy takes constant time, so it does not affect the time complexity.

Space Complexity: O(1)

The space complexity of this algorithm is O(1), since we only need to store the counter variable count which uses constant space.

Code:

Here is the Python implementation of the above algorithm:

def countLatticePoints(x: int, y: int, r: int) -> int: count = 0 for i in range(-r, r+1): for j in range(-r, r+1): if ii + jj <= r*r: count += 1 return count

Time complexity: O(r^2)

Space Complexity: O(1)

1