#2249

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Lattice Points Inside a Circle

Count the number of lattice points inside at least one circle in a grid, based on given center and radius data.

array hash table math geometry enumeration

Problem Statement

You are given a 2D integer array circles, where each circle is represented by three values [xi, yi, ri]. These represent the center (xi, yi) and radius ri of the ith circle drawn on a grid. Your task is to return the number of distinct lattice points that are inside at least one of these circles.

A lattice point is a point with integer coordinates (x, y). A point is inside a circle if the Euclidean distance from the point to the circle's center is less than or equal to the circle's radius. You must consider multiple circles, ensuring that lattice points shared by multiple circles are counted only once.

Examples

Example 1

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

Output: 5

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

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

Solution Approach

Array Scanning

To solve this problem, start by iterating over all possible lattice points within the bounds of the largest circle. For each point, check whether it lies inside any of the circles by evaluating the Euclidean distance from the point to the circle's center.

Hash Set for Uniqueness

Using a hash set allows you to keep track of the distinct lattice points that are inside at least one circle. For each point inside any circle, add it to the set to ensure no duplicates are counted.

Optimization Using Circle Boundaries

Rather than iterating over all possible points in the grid, narrow the search to areas where lattice points can potentially be inside the given circles. This reduces the number of unnecessary checks and improves efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of circles and the area covered by each circle. The space complexity is primarily determined by the hash set storing unique points, which could be up to the total number of points within all circles' bounds.

What Interviewers Usually Probe

Ability to optimize array scanning and hash lookups.
Focus on counting unique lattice points across multiple circles.
Understanding of geometric relationships between points and circles.

Common Pitfalls or Variants

Common pitfalls

Failing to ensure points inside multiple circles are counted only once.
Overlooking the need to check multiple circles for each point.
Not optimizing the range of points to check, leading to excessive computation.

Follow-up variants

Count lattice points inside multiple circles with different sizes.
Consider dynamic radius or center changes for each circle.
Extend the problem to consider other geometric shapes, like ellipses.

FAQ

What is the pattern used in 'Count Lattice Points Inside a Circle'?

The primary pattern involves array scanning plus hash lookup to count unique lattice points inside any given circle.

How do I ensure lattice points are only counted once?

Use a hash set to store unique points and add points only if they are not already in the set.

Can I optimize the range of points I check for each circle?

Yes, you can reduce unnecessary checks by focusing on areas where the lattice points may lie inside the given circles.

How do I check if a point is inside a circle?

For a point (x, y) to be inside a circle with center (xi, yi) and radius ri, the condition (x - xi)^2 + (y - yi)^2 <= ri^2 must hold.

How does GhostInterview help with this problem?

GhostInterview assists by providing optimized solution strategies, including efficient array scanning, hash lookups, and guidance on managing geometric constraints.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = 0
        mx = max(x + r for x, _, r in circles)
        my = max(y + r for _, y, r in circles)
        for i in range(mx + 1):
            for j in range(my + 1):
                for x, y, r in circles:
                    dx, dy = i - x, j - y
                    if dx * dx + dy * dy <= r * r:
                        ans += 1
                        break
        return ans

Continue Practicing

#3588 find maximum area of a triangle #3025 find the number of ways to place people i #3027 find the number of ways to place people ii