Problem Description

You are given a 2D integer array circles where each element circles[i] = [xi, yi, ri] represents a circle on a grid. The circle has its center at coordinates (xi, yi) and has radius ri.

Your task is to count the total number of lattice points that are inside at least one of these circles.

A lattice point is simply a point that has integer coordinates (like (1, 2), (0, 0), (-3, 5), etc.).

Important notes:

• If a point lies exactly on the circumference (boundary) of a circle, it counts as being inside that circle
• A point only needs to be inside at least one circle to be counted (if it's inside multiple circles, it's still counted only once)
• A point (x, y) is inside a circle with center (xi, yi) and radius ri if the distance from the point to the center is less than or equal to the radius, which can be checked using the formula: (x - xi)² + (y - yi)² ≤ ri²

For example, if you have a circle centered at (2, 2) with radius 2, the lattice points inside would include (2, 2) (the center), (2, 0) (on the boundary), (1, 1), (3, 3), and several others.

The solution iterates through all possible lattice points within the bounding box that could potentially be inside any circle (from (0, 0) to the maximum x and y coordinates that any circle could reach), checks if each point is inside at least one circle, and counts the total number of such points.

Intuition

The key insight is that we need to find all integer-coordinate points that fall inside at least one circle. Since we're dealing with integer coordinates, we can use a brute-force approach by checking every possible lattice point.

First, we need to determine the search space. We don't need to check infinite points - we only need to check points that could possibly be inside any of our circles. The furthest a circle can extend from the origin is when its center is at (x, y) with radius r, reaching up to x + r horizontally and y + r vertically. By finding the maximum extent across all circles, we establish our search boundary.

For each lattice point (i, j) in this bounded region, we check if it's inside any circle. To determine if a point is inside a circle, we use the distance formula. A point (i, j) is inside or on a circle with center (x, y) and radius r if the distance from the point to the center is at most r. Using the Pythagorean theorem, this translates to checking if (i - x)² + (j - y)² ≤ r².

The clever part of the solution is that once we find that a point is inside at least one circle, we can immediately count it and move on to the next point (using the break statement). We don't need to check the remaining circles for that point since we only care about whether it's inside at least one circle, not how many.

This brute-force approach works well when the circles are relatively small and the number of lattice points to check is manageable. The time complexity depends on the area covered by the circles rather than just the number of circles.

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward brute-force approach with three nested loops:

Step 1: Determine the search boundary

mx = max(x + r for x, _, r in circles)
my = max(y + r for _, y, r in circles)

We calculate the maximum x-coordinate (mx) and y-coordinate (my) that any circle can reach. This is done by finding the maximum value of x + r (rightmost point) and y + r (topmost point) across all circles. This ensures we check all points that could possibly be inside any circle.

Step 2: Iterate through all lattice points in the bounded region

for i in range(mx + 1):
    for j in range(my + 1):

We iterate through all integer coordinates from (0, 0) to (mx, my). The +1 in the range ensures we include the boundary points.

Step 3: Check if each point is inside any circle

for x, y, r in circles:
    dx, dy = i - x, j - y
    if dx * dx + dy * dy <= r * r:
        ans += 1
        break

For each lattice point (i, j), we check against all circles:

• Calculate the horizontal distance dx = i - x and vertical distance dy = j - y from the point to the circle's center
• Check if dx² + dy² ≤ r² (the squared distance is at most the squared radius)
• If the point is inside or on the boundary of any circle, increment the counter and immediately break to avoid counting the same point multiple times

The algorithm efficiently counts each valid lattice point exactly once, returning the total count of all lattice points that are inside at least one circle.

The time complexity is O(mx × my × n) where n is the number of circles, and the space complexity is O(1) as we only use a counter variable.

Example Walkthrough

Let's walk through a simple example with circles = [[2, 2, 1], [3, 4, 1]].

Step 1: Determine search boundary

• First circle: center (2, 2), radius 1 → can reach x = 2+1 = 3, y = 2+1 = 3
• Second circle: center (3, 4), radius 1 → can reach x = 3+1 = 4, y = 4+1 = 5
• Maximum bounds: mx = 4, my = 5

Step 2: Check each lattice point from (0,0) to (4,5)

Let's trace through some key points:

Point (2, 2):

• Check circle 1: dx = 2-2 = 0, dy = 2-2 = 0
• Distance² = 0² + 0² = 0 ≤ 1² ✓
• Count = 1, break (no need to check circle 2)

Point (2, 3):

• Check circle 1: dx = 2-2 = 0, dy = 3-2 = 1
• Distance² = 0² + 1² = 1 ≤ 1² ✓
• Count = 2, break

Point (3, 3):

• Check circle 1: dx = 3-2 = 1, dy = 3-2 = 1
• Distance² = 1² + 1² = 2 > 1² ✗
• Check circle 2: dx = 3-3 = 0, dy = 3-4 = -1
• Distance² = 0² + (-1)² = 1 ≤ 1² ✓
• Count = 3, break

Point (0, 0):

• Check circle 1: dx = 0-2 = -2, dy = 0-2 = -2
• Distance² = (-2)² + (-2)² = 8 > 1² ✗
• Check circle 2: dx = 0-3 = -3, dy = 0-4 = -4
• Distance² = (-3)² + (-4)² = 25 > 1² ✗
• Not inside any circle, skip

Continuing this process for all points in the grid, the lattice points inside at least one circle are:

• Circle 1: (1,2), (2,1), (2,2), (2,3), (3,2)
• Circle 2: (2,4), (3,3), (3,4), (3,5), (4,4)

Total unique points = 10 (points are counted only once even if they appear in multiple circles)

Solution Implementation

Time and Space Complexity

Time Complexity: O(X * Y * n) where X is the maximum x-coordinate that needs to be checked (max of x + r across all circles), Y is the maximum y-coordinate that needs to be checked (max of y + r across all circles), and n is the number of circles.

• The outer two loops iterate through all possible lattice points from (0, 0) to (mx, my), which gives us O(X * Y) iterations
• For each lattice point, we iterate through all n circles to check if the point lies within any circle
• The distance calculation dx * dx + dy * dy <= r * r is O(1)
• In the worst case, we check all circles for each point before finding one that contains it (or determining none do)
• Total: O(X * Y * n)

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space
• Variables ans, mx, my, i, j, x, y, r, dx, and dy all use O(1) space
• No additional data structures are created that scale with input size
• The input list circles is not counted as it's part of the input

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Consider Negative Coordinates

The current solution only checks points from (0, 0) to (max_x, max_y), which misses all lattice points in negative coordinate regions. If a circle is centered at (1, 1) with radius 3, it covers points like (-1, 0), (-2, 1), etc., which won't be counted.

Fix: Calculate both minimum and maximum bounds for x and y coordinates:

min_x = min(center_x - radius for center_x, _, radius in circles)
max_x = max(center_x + radius for center_x, _, radius in circles)
min_y = min(center_y - radius for _, center_y, radius in circles)
max_y = max(center_y + radius for _, center_y, radius in circles)

for x_coord in range(min_x, max_x + 1):
    for y_coord in range(min_y, max_y + 1):
        # ... rest of the logic

2. Integer Overflow in Distance Calculation

When calculating delta_x * delta_x + delta_y * delta_y, the multiplication can cause integer overflow for very large coordinate values or radii, leading to incorrect results.

Fix: Use careful bounds checking or consider using Python's unlimited precision integers (which is automatic in Python 3), or add explicit overflow checks in other languages.

3. Using Floating-Point Arithmetic

Some might be tempted to use sqrt((x-xi)² + (y-yi)²) <= r with floating-point square root, which can introduce precision errors and make boundary cases unreliable.

Fix: Always use squared distances as shown in the solution: dx * dx + dy * dy <= r * r to maintain integer arithmetic and avoid precision issues.

4. Not Breaking After Finding a Match

Forgetting the break statement after finding that a point is inside a circle would cause the same point to be counted multiple times if it's inside multiple circles.

Fix: Always include break after incrementing the counter to ensure each point is counted exactly once.