Count Lattice Points Inside a Circle — Problem & Solution
Count Lattice Points Inside a Circle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Lattice Points Inside a Circle is a medium coding problem on arrays, hash table and math, asked in Amazon and Rubrik interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Enumeration, Geometry
- Asked at: Amazon, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
circles[i] = [xi, yi, ri] is a circle with centre (xi, yi) and radius ri. A lattice point is a point whose coordinates are both integers.
Return the number of distinct lattice points that lie inside at least one circle. Points on a circle's boundary count as inside.
Example 1
Input: circles = [[3,3,1]]
Output: 5
Explanation: The centre and its four neighbours at distance 1.
Example 2
Input: circles = [[2,2,2]]
Output: 13
Example 3
Input: circles = [[2,2,1],[4,2,1]]
Output: 9
Explanation: Each circle covers 5 points and they share (3, 2).
Constraints
1 <= circles.length <= 200circles[i].length == 31 <= xi, yi <= 1001 <= ri <= min(xi, yi)
Hints for Count Lattice Points Inside a Circle
Hint 1
Every covered point lies within
[0, 200]in both coordinates, a grid of only 201 × 201.Hint 2
Visiting every grid point for every circle works, but you only need to visit each circle's own bounding square.
Hint 3
Mark covered points in a boolean grid so a point inside several circles is counted once.
How to solve Count Lattice Points Inside a Circle
The circles live in a small box, so mark every lattice point each circle covers in a boolean grid and count the distinct marks.
Approach
- Create a 201 × 201 boolean grid (coordinates 0 to 200) and a counter.
- For each circle
[x, y, r], loopifromx - rtox + randjfromy - rtoy + r. - If
(i - x)² + (j - y)² <= r²and the cell is unmarked, mark it and increment the counter. - Return the counter.
Why it works
A lattice point inside circle [x, y, r] has |i - x| <= r and |j - y| <= r, so the bounding square contains every candidate; the squared-distance test selects exactly the points in the closed disk. The constraint r <= min(x, y) with x, y <= 100 keeps every candidate in [0, 200], so the grid is never indexed out of range. Marking before counting ensures a point shared by several circles is counted once.
Complexity
- Time —
O(Σ (2r + 1)²) — at most 200 · 201² checks - Space —
O(201²)
Pitfalls
- Counting per circle and summing double-counts points in overlaps; mark first.
- Include the boundary (
<=). - Use the bounding square of each circle, not the whole grid per circle, if you want it fast.
Reference solution
Python
from typing import List
def countLatticePoints(circles: List[List[int]]) -> int:
seen = bytearray(201 * 201)
count = 0
for x, y, r in circles:
rr = r * r
for i in range(x - r, x + r + 1):
dx2 = (i - x) * (i - x)
base = i * 201
for j in range(y - r, y + r + 1):
if dx2 + (j - y) * (j - y) <= rr and not seen[base + j]:
seen[base + j] = 1
count += 1
return countJava
public static int countLatticePoints(int[][] circles) {
boolean[] seen = new boolean[201 * 201];
int count = 0;
for (int[] c : circles) {
int x = c[0], y = c[1], r = c[2], rr = r * r;
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if ((i - x) * (i - x) + (j - y) * (j - y) <= rr && !seen[i * 201 + j]) {
seen[i * 201 + j] = true;
count++;
}
}
}
}
return count;
}C++
int countLatticePoints(vector<vector<int>>& circles) {
vector<char> seen(201 * 201, 0);
int count = 0;
for (auto& c : circles) {
int x = c[0], y = c[1], r = c[2], rr = r * r;
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if ((i - x) * (i - x) + (j - y) * (j - y) <= rr && !seen[i * 201 + j]) {
seen[i * 201 + j] = 1;
count++;
}
}
}
}
return count;
}JavaScript
var countLatticePoints = function(circles) {
var seen = new Uint8Array(201 * 201);
var count = 0;
for (var c = 0; c < circles.length; c++) {
var x = circles[c][0], y = circles[c][1], r = circles[c][2], rr = r * r;
for (var i = x - r; i <= x + r; i++) {
for (var j = y - r; j <= y + r; j++) {
if ((i - x) * (i - x) + (j - y) * (j - y) <= rr && !seen[i * 201 + j]) {
seen[i * 201 + j] = 1;
count++;
}
}
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets