Is Count Lattice Points Inside a Circle easy or hard?

The problem is rated Medium because the main difficulty is recognizing that you only need to search within each circle's bounding region and handle overlapping points correctly. The math itself is simple, but efficient enumeration and deduplication require careful implementation.

Count Lattice Points Inside a Circle Python/Java solution

Python, Java, C++, and other languages implement the same idea: iterate through the circle's bounding region, verify the equation (x − cx)² + (y − cy)² ≤ r², and store valid points in a set. Python typically uses a tuple set, while Java often uses a HashSet with encoded coordinates.

How to solve Count Lattice Points Inside a Circle in O(n · r²)?

Iterate through the x-range of each circle from cx − r to cx + r. For each x, compute the maximum vertical distance using sqrt(r² − dx²). Enumerate the y values in that range and insert each lattice point into a hash set. The set automatically removes duplicates when circles overlap.

What is the best approach for Count Lattice Points Inside a Circle?

The optimized bounded search approach is typically the best solution. Instead of checking every point in the bounding square, compute the valid vertical range using the circle equation dy ≤ sqrt(r² − dx²). This reduces unnecessary distance checks while still enumerating all valid lattice points. Time complexity remains O(n · r²) with O(k) space for storing unique points.

Is Count Lattice Points Inside a Circle asked at Google/Amazon/Meta?

Geometry and grid enumeration problems like this appear frequently in technical interviews at companies such as Google, Amazon, and Meta. While the exact problem may vary, the pattern of using distance formulas, bounding regions, and hash sets for deduplication is common.

What data structure is used in Count Lattice Points Inside a Circle?

A hash set is the main data structure used to store visited lattice points. Each point is encoded as a pair (x, y) so overlapping circles do not double count the same coordinate. The algorithm also relies on basic math operations and geometric distance checks.

What is the time complexity of Count Lattice Points Inside a Circle?

Most practical solutions run in O(n · r²) time, where n is the number of circles and r is the radius. Each circle only explores its local bounding region instead of the entire grid. A hash set is used to ensure lattice points covered by multiple circles are counted once.

Description Hints 2 Solution Video 6:21

2249. Count Lattice Points Inside a Circle

Medium57.1% acceptance1 company

Given a 2D integer array circles where circles[i] = [x_i, y_i, r_i] represents the center (x_i, y_i) and radius r_i of the i^th circle drawn on a grid, return the number of lattice points that are present inside at least one circle.

Note:

A lattice point is a point with integer coordinates.
Points that lie on the circumference of a circle are also considered to be inside it.

Example 1:

Input: circles = [[2,2,1]]
Output: 5
Explanation:
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

Example 2:

Input: circles = [[2,2,2],[3,4,1]]
Output: 16
Explanation:
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

Constraints:

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

Asked at 1 company

Rubrik

Topics

Hints open one at a time

Hint 1

For each circle, how can you check whether or not a lattice point lies inside it?

Hint 2

Since you need to reduce the search space, consider the minimum and maximum possible values of the coordinates of a lattice point contained in any circle.

6:21

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution