Count Lattice Points Inside a Circle solution and explanation
7 more videos on this problem
Count Lattice Points Inside a Circle | Leetcode 2249 | Maths | Contest 290 🔥🔥Coding Decoded · 6:21 · 2K views
2249. Count Lattice Points Inside a Circle || Leetcode Weekly Contest 290 || Leetcode 2249Bro Coders · 9:13 · 2K views
2249. Count Lattice Points Inside a Circle (Leetcode Medium)Programming Live with Larry · 8:44 · 690 views
Leetcode Weekly-contest-290 - Count Lattice Points Inside a CirclePrakhar Agrawal · 8:05 · 373 views
2249. Count Lattice Points Inside a Circle | Leetcode weekly 290 | Leetcode Medium| LeetcodeBinaryMagic · 12:57 · 176 views
Count Lattice Points Inside a Circle - Solution to Leetcode medium problem with explanation - DSATHE CODE CLUB · 9:01 · 107 views
LeetCode 2249 count lattice points inside a circle[CE] Code Engineering · 17:00 · 52 views
Leetcode 2249. Count Lattice Points Inside a Circle (geometry)LetsCode · 7:55 · 42 views
The problem
Given a 2D integer array circles where circles[i] = [xi, yi, ri] represents the center (xi, yi) and radius ri of the ith 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 <= 200circles[i].length == 31 <= xi, yi <= 1001 <= ri <= min(xi, yi)
Approach overview
Problem Overview: You are given multiple circles on a 2D grid where each circle is defined by (x, y, r). The task is to count how many integer lattice points lie inside at least one circle. A lattice point (i, j) is inside a circle if (i - x)^2 + (j - y)^2 ≤ r^2.
Approach 1: Brute Force with Bounding Box (Time: O(n · r²), Space: O(k))
Each circle defines a square bounding box from x - r to x + r and y - r to y + r. Iterate through every integer coordinate inside this box and check the circle equation (dx * dx + dy * dy ≤ r²). If the point lies inside the circle, store it in a hash set to avoid counting duplicates from overlapping circles. This method relies on simple geometry and grid enumeration. The approach is straightforward to implement and works well because the radius is relatively small, but it still scans many unnecessary points in the bounding square.
Approach 2: Efficient Bounded Search with Optimization (Time: O(n · r²), Space: O(k))
This version still limits exploration to each circle's bounding square but reduces redundant checks by focusing only on coordinates that could realistically satisfy the circle equation. For every x in the horizontal range [cx - r, cx + r], compute the maximum vertical distance allowed by rearranging the equation: dy ≤ sqrt(r² - dx²). Then enumerate only the valid y values within that vertical span. Each discovered lattice point is inserted into a set (using a hash table) so overlapping circles do not double count points. This cuts many unnecessary distance checks and performs well even when circles overlap heavily.
Recommended for interviews: Start with the bounding-box brute force to demonstrate the geometric condition and enumeration logic. Interviewers usually expect the optimized bounded search afterward. The optimization shows that you can manipulate the circle equation and reduce the search area while still guaranteeing correctness.
Approach 1: Brute Force with Bounding Box
This approach entails examining each point within the bounding box of each circle. For every point, we check whether it lies inside the circle using the equation of a circle.
The brute force solution may not be optimal but it's straightforward and ensures that we capture all lattice points within the circles.
def countLatticePoints(circles):
points = set()
for x, y, r in circles:
for dx in range(-r, r+1):
for dy in range(-r, r+1):
if dx ** 2 + dy ** 2 <= r ** 2:
points.add((x + dx, y + dy))
return len(points)
# Example
circles = [[2, 2, 1]]
print(countLatticePoints(circles)) # Output: 5import java.util.HashSet;
import java.util.Set;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Integer.hashCode(x) ^ Integer.hashCode(y);
}
}
public class Solution {
public int countLatticePoints(int[][] circles) {
Set<Point> set = new HashSet<>();
for (int[] circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = -r; dx <= r; dx++) {
for (int dy = -r; dy <= r; dy++) {
if (dx * dx + dy * dy <= r * r) {
set.add(new Point(x + dx, y + dy));
}
}
}
}
return set.size();
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] circles = {{2, 2, 1}};
System.out.println(sol.countLatticePoints(circles)); // Output: 5
}
}#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
struct Hash {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ hash<int>()(p.y);
}
};
int countLatticePoints(vector<vector<int>>& circles) {
unordered_set<Point, Hash> points;
for (const auto& circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = -r; dx <= r; ++dx) {
for (int dy = -r; dy <= r; ++dy) {
if (dx * dx + dy * dy <= r * r) {
points.insert({x + dx, y + dy});
}
}
}
}
return points.size();
}
int main() {
vector<vector<int>> circles = {{2,2,1}};
cout << countLatticePoints(circles) << endl; // Output: 5
return 0;
}var countLatticePoints = function (circles) {
const points = new Set();
for (const [x, y, r] of circles) {
for (let dx = -r; dx <= r; dx++) {
for (let dy = -r; dy <= r; dy++) {
if (dx * dx + dy * dy <= r * r) {
points.add(`${x + dx},${y + dy}`);
}
}
}
}
return points.size;
};
// Example usage:
const circles = [[2, 2, 1]];
console.log(countLatticePoints(circles)); // Output: 5#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <set>
int countLatticePoints(int** circles, int circlesSize) {
struct Point {
int x, y;
bool operator<(const Point& a) const {
return x == a.x ? y < a.y : x < a.x;
}
};
std::set<Point> points;
for (int i = 0; i < circlesSize; ++i) {
int x = circles[i][0], y = circles[i][1], r = circles[i][2];
for (int dx = -r; dx <= r; ++dx) {
for (int dy = -r; dy <= r; ++dy) {
if (dx * dx + dy * dy <= r * r) {
Point p = { x + dx, y + dy };
points.insert(p);
}
}
}
}
return points.size();
}using System;
using System.Collections.Generic;
public class Solution {
private struct Point {
public int x, y;
public Point(int x, int y) {
this.x = x; this.y = y;
}
}
public int CountLatticePoints(int[][] circles) {
HashSet<Point> points = new HashSet<Point>();
foreach (var circle in circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = -r; dx <= r; dx++) {
for (int dy = -r; dy <= r; dy++) {
if (dx * dx + dy * dy <= r * r) {
points.Add(new Point(x + dx, y + dy));
}
}
}
}
return points.Count;
}
public static void Main() {
Solution solution = new Solution();
int[][] circles = new int[][] { new int[] {2, 2, 1} };
Console.WriteLine(solution.CountLatticePoints(circles)); // Output: 5
}
}The Python approach utilizes a set to efficiently track distinct lattice points. It iterates over each possible point within the bounding box derived from the circle radius and checks if the point lies within the circle before recording it.
Time Complexity: O(n * r^2)
Space Complexity: O(n * r^2)
Approach 2: Efficient Bounded Search with Optimization
In this approach, we exploit the properties of circles and symmetry for optimization. We limit the lattice point evaluation to only one quadrant and reflect results to others, reducing computation time.
import math
def countLatticePoints(circles):
points = set()
for x, y, r in circles:
for dx in range(r + 1):
dy = int(math.sqrt(r * r - dx * dx))
for sign_y in [-1, 1]:
for sign_x in [-1, 1]:
points.add((x + dx * sign_x, y + dy * sign_y))
points.add((x + dy * sign_y, y + dx * sign_x))
return len(points)
# Example
circles = [[2, 2, 1]]
print(countLatticePoints(circles)) # Output: 5import java.util.HashSet;
import java.util.Set;
import static java.lang.Math.*;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Integer.hashCode(x) ^ Integer.hashCode(y);
}
}
public class Solution {
public int countLatticePoints(int[][] circles) {
Set<Point> set = new HashSet<>();
for (int[] circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = 0; dx <= r; dx++) {
int dy = (int)floor(sqrt(r * r - dx * dx));
for (int signY = -1; signY <= 1; signY += 2) {
for (int signX = -1; signX <= 1; signX += 2) {
set.add(new Point(x + dx * signX, y + dy * signY));
set.add(new Point(x + dy * signY, y + dx * signX));
}
}
}
}
return set.size();
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] circles = {{2, 2, 1}};
System.out.println(sol.countLatticePoints(circles)); // Output: 5
}
}#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
struct Hash {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ hash<int>()(p.y);
}
};
int countLatticePoints(vector<vector<int>>& circles) {
unordered_set<Point, Hash> points;
for (const auto& circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = 0; dx <= r; ++dx) {
int dy = floor(sqrt(r * r - dx * dx));
for (int sign_y = -1; sign_y <= 1; sign_y += 2) {
for (int sign_x = -1; sign_x <= 1; sign_x += 2) {
points.insert({x + dx * sign_x, y + dy * sign_y});
points.insert({x + dy * sign_y, y + dx * sign_x});
}
}
}
}
return points.size();
}
int main() {
vector<vector<int>> circles = {{2,2,1}};
cout<<countLatticePoints(circles)<<endl; //5
return 0;
}var countLatticePoints = function (circles) {
const points = new Set();
for (const [x, y, r] of circles) {
for (let dx = 0; dx <= r; dx++) {
const dy = Math.floor(Math.sqrt(r * r - dx * dx));
for (let signY = -1; signY <= 1; signY += 2) {
for (let signX = -1; signX <= 1; signX += 2) {
points.add(`${x + dx * signX},${y + dy * signY}`);
points.add(`${x + dy * signY},${y + dx * signX}`);
}
}
}
}
return points.size;
};
// Example usage:
const circles = [[2, 2, 1]];
console.log(countLatticePoints(circles)); // Output: 5#include <stdio.h>
#include <math.h>
#include <set>
struct Point {
int x, y;
bool operator<(const Point& a) const {
return x == a.x ? y < a.y : x < a.x;
}
};
int countLatticePoints(int** circles, int circlesSize) {
std::set<Point> points;
for (int i = 0; i < circlesSize; ++i) {
int x = circles[i][0], y = circles[i][1], r = circles[i][2];
for (int dx = 0; dx <= r; ++dx) {
int dy = floor(sqrt(r * r - dx * dx));
for (int sign_y = -1; sign_y <= 1; sign_y += 2) {
for (int sign_x = -1; sign_x <= 1; sign_x += 2) {
points.insert({x + dx * sign_x, y + dy * sign_y});
points.insert({x + dy * sign_y, y + dx * sign_x});
}
}
}
}
return points.size();
}using System;
using System.Collections.Generic;
public class Solution {
private struct Point {
public int x, y;
public Point(int x, int y) {
this.x = x; this.y = y;
}
}
public int CountLatticePoints(int[][] circles) {
HashSet<Point> points = new HashSet<Point>();
foreach (var circle in circles) {
int x = circle[0], y = circle[1], r = circle[2];
for (int dx = 0; dx <= r; dx++) {
int dy = (int)Math.Floor(Math.Sqrt(r * r - dx * dx));
for (int signY = -1; signY <= 1; signY += 2) {
for (int signX = -1; signX <= 1; signX += 2) {
points.Add(new Point(x + dx * signX, y + dy * signY));
points.Add(new Point(x + dy * signY, y + dx * signX));
}
}
}
}
return points.Count;
}
public static void Main() {
Solution solution = new Solution();
int[][] circles = new int[][] { new int[] {2, 2, 1} };
Console.WriteLine(solution.CountLatticePoints(circles)); // Output: 5
}
}Python leverages the math library to compute dy using Math.sqrt. The points are identified and recorded efficiently by examining only one quadrant and employing symmetry to infer additional lattice points.
Time Complexity: O(n * r)
Space Complexity: O(n * r^2)
Approach 3: Default Approach
function countLatticePoints(circles: number[][]): number {
let mx = 0;
let my = 0;
for (const [x, y, r] of circles) {
mx = Math.max(mx, x + r);
my = Math.max(my, y + r);
}
let ans = 0;
for (let i = 0; i <= mx; ++i) {
for (let j = 0; j <= my; ++j) {
for (const [x, y, r] of circles) {
const dx = i - x;
const dy = j - y;
if (dx * dx + dy * dy <= r * r) {
++ans;
break;
}
}
}
}
return ans;
}func countLatticePoints(circles [][]int) (ans int) {
mx, my := 0, 0
for _, c := range circles {
mx = max(mx, c[0]+c[2])
my = max(my, c[1]+c[2])
}
for i := 0; i <= mx; i++ {
for j := 0; j <= my; j++ {
for _, c := range circles {
dx, dy := i-c[0], j-c[1]
if dx*dx+dy*dy <= c[2]*c[2] {
ans++
break
}
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Bounding Box | Time Complexity: O(n * r^2) |
| Efficient Bounded Search with Optimization | Time Complexity: O(n * r) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Bounding Box | O(n · r²) | O(k) | Good starting approach. Simple geometry check for every grid point in the bounding square. |
| Efficient Bounded Search with Optimization | O(n · r²) | O(k) | Preferred solution. Reduces unnecessary checks by computing valid vertical ranges using the circle equation. |
Frequently asked questions
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.