LeetCode 2249 - Count Lattice Points Inside a Circle

The problem asks us to determine how many lattice points lie inside at least one of a set of circles on a 2D grid. Each circle is represented by a triplet [xi, yi, ri], where (xi, yi) is the circle's center and ri is its radius.

leetcodemediumarrayhash-tablemathgeometryenumeration

LeetCode Problem 2249

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Geometry, Enumeration

Solution

Problem Understanding

The problem asks us to determine how many lattice points lie inside at least one of a set of circles on a 2D grid. Each circle is represented by a triplet [xi, yi, ri], where (xi, yi) is the circle's center and ri is its radius. A lattice point is any point on the grid with integer coordinates (x, y). Points that lie exactly on the circumference of a circle are considered inside.

Given that 1 <= xi, yi <= 100 and 1 <= ri <= min(xi, yi), all circles are confined within the first quadrant grid from (1, 1) to (100, 100). There are at most 200 circles, so the total computation must remain efficient for grids of size up to 100 x 100.

Edge cases include circles of radius 1 (single-point coverage), overlapping circles, circles near the boundary of the grid, and multiple circles with identical centers. A naive approach must consider overlapping lattice points carefully to avoid double counting.

Approaches

The brute-force method would iterate over every point in the grid (from (0,0) to (100,100)) and check whether each point lies inside any circle. This guarantees correctness because it explicitly checks all possible lattice points. However, it may be inefficient because for each point, it iterates through all circles, resulting in O(100^2 * n) time complexity, which is acceptable but not optimal.

A more optimal observation is that the number of lattice points inside a circle of radius r is limited to the bounding square [x-r, x+r] x [y-r, y+r]. Instead of checking every point in the entire grid, we only iterate over this bounding box for each circle. Using a set to store discovered lattice points automatically handles duplicates when circles overlap.

Approach Time Complexity Space Complexity Notes
Brute Force O(100 * 100 * n) O(1) Checks every grid point against every circle
Optimal O(n * r^2) O(number of lattice points) Iterates only through bounding box of each circle and stores points in a set

Algorithm Walkthrough

  1. Initialize an empty set to store unique lattice points.
  2. For each circle [cx, cy, r] in the input list, compute the bounding box of possible lattice points as [cx-r, cx+r] for x and [cy-r, cy+r] for y.
  3. Iterate over all integer coordinates (x, y) in this bounding box.
  4. For each (x, y), check if it lies inside or on the circle using the Euclidean distance squared: (x - cx)^2 + (y - cy)^2 <= r^2.
  5. If the point satisfies the condition, add it to the set.
  6. After processing all circles, the number of lattice points is simply the size of the set.

Why it works: The set ensures that overlapping points are counted only once. Checking within the bounding box of each circle reduces unnecessary computations while ensuring no lattice point inside the circle is missed.

Python Solution

from typing import List

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        lattice_points = set()
        
        for cx, cy, r in circles:
            for x in range(cx - r, cx + r + 1):
                for y in range(cy - r, cy + r + 1):
                    if (x - cx) ** 2 + (y - cy) ** 2 <= r ** 2:
                        lattice_points.add((x, y))
        
        return len(lattice_points)

The implementation first creates a set lattice_points to store all unique points. For each circle, we iterate only over points that lie in its bounding square. The squared Euclidean distance avoids floating-point operations and ensures exact checks. The set naturally avoids counting duplicates from overlapping circles.

Go Solution

func countLatticePoints(circles [][]int) int {
    latticePoints := make(map[[2]int]struct{})
    
    for _, circle := range circles {
        cx, cy, r := circle[0], circle[1], circle[2]
        for x := cx - r; x <= cx + r; x++ {
            for y := cy - r; y <= cy + r; y++ {
                dx := x - cx
                dy := y - cy
                if dx*dx + dy*dy <= r*r {
                    latticePoints[[2]int{x, y}] = struct{}{}
                }
            }
        }
    }
    
    return len(latticePoints)
}

The Go implementation uses a map with keys as [2]int arrays to mimic a set. Each point inside the circle is added as a key. Duplicate points are automatically ignored due to the map's key uniqueness property.

Worked Examples

Example 1: circles = [[2,2,1]]

The bounding box is x ∈ [1, 3], y ∈ [1, 3]. Iterating over all points:

Point (x, y) Distance Squared Inside?
(1, 1) 2 No
(1, 2) 1 Yes
(1, 3) 2 No
(2, 1) 1 Yes
(2, 2) 0 Yes
(2, 3) 1 Yes
(3, 1) 2 No
(3, 2) 1 Yes
(3, 3) 2 No

Unique points inside: 5.

Example 2: circles = [[2,2,2],[3,4,1]]

Bounding box for first circle: x ∈ [0, 4], y ∈ [0, 4]. For second circle: x ∈ [2, 4], y ∈ [3, 5]. After adding all lattice points in these bounding boxes, the set size is 16.

Complexity Analysis

Measure Complexity Explanation
Time O(n * r^2) For each circle, iterate over its bounding square which has at most (2r+1)^2 points
Space O(number of lattice points) Storing all unique points in a set/map

Since r <= 100 and n <= 200, this is efficient enough. The actual number of lattice points is bounded by the total area covered by all circles.

Test Cases

# Provided examples
assert Solution().countLatticePoints([[2,2,1]]) == 5  # single small circle
assert Solution().countLatticePoints([[2,2,2],[3,4,1]]) == 16  # overlapping circles

# Edge cases
assert Solution().countLatticePoints([[1,1,1]]) == 3  # circle at grid origin edge
assert Solution().countLatticePoints([[100,100,1]]) == 3  # circle at opposite corner
assert Solution().countLatticePoints([[2,2,1],[2,2,1]]) == 5  # duplicate circles
assert Solution().countLatticePoints([[50,50,50]]) == 7801  # large circle covering many points
Test Why
[[2,2,1]] Validates single small circle computation
[[2,2,2],[3,4,1]] Validates overlapping circles
[[1,1,1]] Tests circle on the boundary of the grid
[[100,100,1]] Tests circle on opposite corner
[[2,2,1],[2,2,1]] Tests duplicate circles handling
[[50,50,50]] Tests large circle covering many points efficiently

Edge Cases

1. Circle at the grid boundary

Circles with centers near (1,1) or (100,100) may have bounding boxes partially outside the grid. The algorithm works correctly since lattice points outside the valid grid are simply counted but do not affect correctness because negative or large coordinates are still valid integers.

2. Overlapping circles

Points covered by multiple circles should be counted only once. Using a set or map guarantees uniqueness, preventing double counting.

3. Large radius circles

For a circle with radius approaching the grid size, the bounding box becomes large. Iterating over (2r+1)^2 points remains feasible because r <= 100 and the total points never exceed 10000 per circle. Using the distance check ensures only points truly inside are counted, avoiding overestimation.

This solution handles all edge cases efficiently and correctly.