Count Lattice Points Inside a Circle

Count Lattice Points Inside a Circle

What is this problem about?

The "Count Lattice Points Inside a Circle" coding problem asks you to find the number of unique points $(x, y)$ with integer coordinates that fall inside or on the boundary of at least one of the given circles. Each circle is defined by its center $(x, y)$ and its radius $r$.

Why is this asked in interviews?

Companies like Rubrik use this problem to test geometric logic and the ability to optimize an enumeration approach. It requires a candidate to define a bounding box for each circle and efficiently check points within that box. It also tests the use of Hash Sets to handle overlapping circles and prevent double-counting points.

Algorithmic pattern used

This is a Geometry and Enumeration problem. For each circle, you determine its "Bounding Box": from $(x-r)$ to $(x+r)$ horizontally and $(y-r)$ to $(y+r)$ vertically. You iterate through every integer point within this box and use the circle equation $(x_i - x_c)^2 + (y_i - y_c)^2 \le r^2$ to check if the point is inside. A global Hash Set stores the string or encoded representation of each valid $(x, y)$ point.

Example explanation

Suppose we have a circle at $(2, 2)$ with radius 1.

• Bounding Box: $x \in [1, 3], y \in [1, 3]$.
• Possible points: (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3).
• Check $(1,1)$: $(1-2)^2 + (1-2)^2 = 1+1 = 2$. $2 > 1^2$, so (1,1) is OUT.
• Check $(2,2)$: $(2-2)^2 + (2-2)^2 = 0$. $0 \le 1^2$, so (2,2) is IN.
• Check $(1,2)$: $(1-2)^2 + (2-2)^2 = 1$. $1 \le 1^2$, so (1,2) is IN. Points inside are: (2,2), (1,2), (3,2), (2,1), (2,3). Total 5.

Common mistakes candidates make

A common error is using floating-point math (like sqrt) which can lead to precision issues. It's always safer to use the squared distance comparison. Another mistake is inefficiently iterating over the entire possible grid range (e.g., 0 to 200) for every circle instead of just the bounding box. Finally, failing to use a set to handle overlapping circles leads to incorrect counts.

Interview preparation tip

When dealing with "unique points" or "unique items" in a 2D space, think about how to represent a coordinate as a single key. You can use a string "x,y" or a bit-shifted long (x << 32 | y) to store points in a Hash Set efficiently.