Count Lattice Points Inside a Circle

Medium
1306.

Count Lattice Points Inside a Circle

Count Lattice Points Inside a Circle is a medium coding problem on arrays, hash table and math, asked in Amazon and Rubrik interviews.

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 <= 200
  • circles[i].length == 3
  • 1 <= xi, yi <= 100
  • 1 <= ri <= min(xi, yi)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} circles
 * @return {number}
 */
var countLatticePoints = function(circles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 200
  • circles[i].length == 3
  • 1 <= xi, yi <= 100
  • 1 <= ri <= min(xi, yi)

Hints for Count Lattice Points Inside a Circle

  1. Hint 1

    Every covered point lies within [0, 200] in both coordinates, a grid of only 201 × 201.

  2. Hint 2

    Visiting every grid point for every circle works, but you only need to visit each circle's own bounding square.

  3. 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

  1. Create a 201 × 201 boolean grid (coordinates 0 to 200) and a counter.
  2. For each circle [x, y, r], loop i from x - r to x + r and j from y - r to y + r.
  3. If (i - x)² + (j - y)² <= r² and the cell is unmarked, mark it and increment the counter.
  4. 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 count

Java

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