Count Connected Clusters of Two-Dimensional Points
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Count Connected Clusters of Two-Dimensional Points
### Problem
Implement `count_clusters(points, radius)`.
`points` is a list of two-dimensional integer coordinates. Two distinct point indices are directly connected when their Euclidean distance is less than or equal to the nonnegative `radius`. Connectivity is transitive: if point A is connected to B and B is connected to C, all three belong to the same cluster even when A and C are farther apart than `radius`.
Return the number of connected clusters. Duplicate coordinates represent distinct points and have distance zero. An empty input has zero clusters.
### Function Contract
Implement the function with this exact argument order:
```text
count_clusters(points, radius) -> integer
```
1. `points` is an array of coordinate pairs in input order. Each pair is `[x, y]`.
2. `radius` is a nonnegative integer.
3. Return one integer: the number of connected clusters. Point order does not change the result.
### Examples
```text
points = [(0, 0), (1, 0), (3, 0), (4, 0)]
radius = 1
result = 2
```
```text
points = [(0, 0), (1, 0), (2, 0)]
radius = 1
result = 1
```
```text
points = [(5, 5), (5, 5), (20, 20)]
radius = 0
result = 2
```
### Required Approach
- First implement the brute-force neighbor search by considering every pair of point indices.
- Avoid square roots by comparing squared distance with `radius * radius`.
- Use DFS, BFS, or disjoint-set union to compute connected components.
- Support `0 <= points.length <= 2,000`.
- Support `-1,000,000,000 <= x, y <= 1,000,000,000` for every point.
- Support `0 <= radius <= 2,000,000,000`.
- Convert coordinates and `radius` to exact signed 64-bit values before subtraction or multiplication. The largest possible squared-distance sum is `8,000,000,000,000,000,000`, which fits in signed 64-bit arithmetic. JavaScript implementations should use `BigInt` for these calculations.
```hint Try a transitive chain
Construct three points where each neighboring pair is within `radius` but the first and third points are not; use that case to decide what information must persist.
```
### Discussion Prompts
1. What are the time and space complexities of the brute-force solution?
2. Why does checking only whether each point has a nearby point fail to count transitive clusters?
3. How could a spatial grid reduce candidate neighbor comparisons for a large point set?
4. What cases become important when `radius` is zero or coordinates are duplicated?
Quick Answer: Count connected clusters of two-dimensional points under a radius threshold, including transitive chains and duplicate coordinates. Practice transitive connectivity, exact distance comparisons, duplicate handling, overflow safety, complexity analysis, and large-scale optimization.
Implement `count_clusters(points, radius)`.
`points` is a list of two-dimensional integer coordinates, each given as `[x, y]`
in input order. Two distinct point indices are **directly connected** when their
Euclidean distance is less than or equal to the nonnegative `radius`. Connectivity
is transitive: if point A is connected to B and B is connected to C, all three
belong to the same cluster even when A and C are farther apart than `radius`.
Return the number of connected clusters as a single integer. Duplicate coordinates
represent distinct points and are distance 0 apart. An empty input has zero
clusters. The result does not depend on the order of `points`, and there is exactly
one correct integer for every input, so no tie-breaking or ordering rule is needed.
### Function contract
```text
count_clusters(points, radius) -> integer
```
1. `points` is an array of coordinate pairs in input order. Each pair is `[x, y]`.
2. `radius` is a nonnegative integer.
3. Return one integer: the number of connected clusters. It is always between 0 and
`len(points)` inclusive.
### Examples
```text
points = [[0, 0], [1, 0], [3, 0], [4, 0]]
radius = 1
result = 2
```
The pairs `[0, 0]`/`[1, 0]` and `[3, 0]`/`[4, 0]` are each 1 apart, but the two
pairs are 2 apart, so there are two clusters.
```text
points = [[0, 0], [1, 0], [2, 0]]
radius = 1
result = 1
```
`[0, 0]` and `[2, 0]` are 2 apart, yet both reach `[1, 0]`, so transitivity puts
all three in one cluster.
```text
points = [[5, 5], [5, 5], [20, 20]]
radius = 0
result = 2
```
The two identical coordinates are distance 0 apart and merge even at radius 0;
`[20, 20]` stays on its own.
### Numeric range
Compare squared distances with `radius * radius` rather than taking a square root.
A coordinate difference reaches 2,000,000,000, so the largest possible squared
distance is 8,000,000,000,000,000,000. That value exceeds 32-bit range and also
exceeds 2^53, so it is not exactly representable as a JavaScript `Number`. Use
exact signed 64-bit arithmetic (`long` in Java, `long long` in C++) and `BigInt`
in JavaScript for the products and their sum. Only the returned cluster count,
at most 2,000, crosses the function boundary.
Constraints
- 0 <= len(points) <= 2000
- len(points[i]) == 2 for every point
- -1000000000 <= points[i][0], points[i][1] <= 1000000000
- 0 <= radius <= 2000000000
- Every coordinate and radius is an integer
- Squared distances reach 8 * 10^18 and radius * radius reaches 4 * 10^18, so intermediate products need exact signed 64-bit arithmetic (BigInt in JavaScript)
- 0 <= returned cluster count <= len(points)
Examples
Input: ([], 0)
Expected Output: 0
Input: ([[7, -3]], 0)
Expected Output: 1
Hints
- Two points are connected exactly when their squared distance is at most radius * radius, so no square root is needed. Decide which integer width holds that product before you write the comparison.
- Counting how many points have a nearby neighbour is not the answer. The relation is transitive, so you need a structure that turns a pairwise 'adjacent' relation into groups: DFS, BFS, or disjoint-set union over the point indices.
- Trace radius = 0 twice, once with two identical coordinates and once with two different ones. The two traces must produce different counts.