Count Lattice Points Inside a Circle - Practice Coding Problems

Count Lattice Points Inside a Circle - 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.

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.

Input & Output

Example 1 — Two Circles with Overlap

$ Input: circles = [[2,2,1],[3,4,1]]

› Output: 16

💡 Note: Circle 1 centered at (2,2) with radius 1 covers points like (1,2), (2,1), (2,2), (2,3), (3,2). Circle 2 centered at (3,4) with radius 1 covers points like (2,4), (3,3), (3,4), (3,5), (4,4). Total unique lattice points is 16.

Example 2 — Single Small Circle

$ Input: circles = [[1,1,1]]

› Output: 5

💡 Note: Circle centered at (1,1) with radius 1 covers lattice points: (0,1), (1,0), (1,1), (1,2), (2,1). Total is 5 points.

Example 3 — Multiple Overlapping Circles

$ Input: circles = [[1,1,1],[2,2,1],[3,3,1]]

› Output: 12

💡 Note: Three circles with radius 1 each, positioned diagonally. Some points are covered by multiple circles but counted only once. Total unique lattice points is 12.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Circles with center coordinates and radius

Process

Find all lattice points inside any circle

Output

Count of unique lattice points

Key Takeaway

🎯 Key Insight: Use distance formula (x-cx)² + (y-cy)² ≤ r² to check if lattice points are inside circles, and handle overlaps with a set

Asked in

G Google 15 M Microsoft 12

The key insight is to use the distance formula to check if lattice points fall within circles. The optimal approach processes each circle individually and uses a set to automatically handle duplicate points. Best approach is Circle-by-Circle with Set: Time O(n × r²), Space O(k) where k is the number of unique points.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Points	O(n × w × h)	O(1)	Check every possible lattice point to see if it's inside any circle
Circle-by-Circle with Set	O(n × r²)	O(k)	For each circle, find all lattice points inside and use a set to avoid duplicates

Brute Force - Check All Points — Algorithm Steps

Step 1: Find the bounding box containing all circles
Step 2: For each lattice point in the bounding box, check if it's inside any circle
Step 3: Count unique points that are inside at least one circle

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Bounding Box

Determine the rectangle that contains all circles

Check Each Point

For every lattice point, test if it's inside any circle

Count Results

Sum up all points that are inside at least one circle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int circles[][3], int n) {
    if (n == 0) return 0;
    
    // Find bounding box
    int minX = INT_MAX, maxX = INT_MIN;
    int minY = INT_MAX, maxY = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        int x = circles[i][0], y = circles[i][1], r = circles[i][2];
        if (x - r < minX) minX = x - r;
        if (x + r > maxX) maxX = x + r;
        if (y - r < minY) minY = y - r;
        if (y + r > maxY) maxY = y + r;
    }
    
    int count = 0;
    
    // Check each lattice point in bounding box
    for (int x = minX; x <= maxX; x++) {
        for (int y = minY; y <= maxY; y++) {
            // Check if this point is inside any circle
            for (int i = 0; i < n; i++) {
                int cx = circles[i][0], cy = circles[i][1], r = circles[i][2];
                long long distSq = (long long)(x - cx) * (x - cx) + (long long)(y - cy) * (y - cy);
                if (distSq <= (long long)r * r) {
                    count++;
                    break;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int circles[1000][3];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    while (ptr && n < 1000) {
        ptr = strchr(ptr + 1, '[');
        if (ptr) {
            sscanf(ptr + 1, "%d,%d,%d", &circles[n][0], &circles[n][1], &circles[n][2]);
            n++;
        }
    }
    
    int result = solution(circles, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × w × h)

For each circle (n), we check all points in bounding box (width × height)

✓ Linear Growth

Space Complexity

O(1)

Only using variables for coordinates, no extra data structures

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler