Katkat
Back

Count Connected Clusters of Two-Dimensional Points

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests modeling geometric proximity as a graph problem, using Disjoint Set Union or graph traversal to identify connected components while ensuring exact integer arithmetic and handling duplicate coordinates.

Count Connected Clusters of Two-Dimensional Points

You are given a list of 2D points on a Cartesian plane, where points[i] = [x_i, y_i], and a non-negative integer r representing a connection radius.

Two points A and B are directly connected if the Euclidean distance between them is less than or equal to r. Additionally, connectivity is transitive: if point A is connected to point B, and point B is connected to point C, then A and C belong to the same cluster.

Duplicate coordinates may appear in the input and should be treated as valid points that occupy the exact same position.

Return the total number of connected clusters formed by these points.

Function Signature

def count_clusters(points: list[list[int]], r: int) -> int:
    pass

Examples

Example 1:

Input: points = [[0, 0], [1, 1], [4, 4], [4, 5]], r = 2
Output: 2
Explanation:
- The squared distance between [0, 0] and [1, 1] is (1 - 0)^2 + (1 - 0)^2 = 2 <= 2^2 (4), so they form a cluster.
- The squared distance between [4, 4] and [4, 5] is (4 - 4)^2 + (5 - 4)^2 = 1 <= 2^2 (4), so they form a cluster.
- There is no path between the two groups, resulting in 2 clusters.

Example 2:

Input: points = [[0, 0], [2, 0], [4, 0]], r = 2
Output: 1
Explanation:
- [0, 0] connects to [2, 0] (distance 2 <= 2).
- [2, 0] connects to [4, 0] (distance 2 <= 2).
- By transitivity, all three points belong to a single cluster.

Constraints

  • 1 <= points.length <= 2000
  • points[i].length == 2
  • -10^6 <= points[i][0], points[i][1] <= 10^6
  • 0 <= r <= 10^6

Edge Cases to Consider

  • r = 0: Only points with identical coordinates will connect.
  • Duplicate points in the input list (their distance is 0 <= r).
  • Long transitive chains where no two endpoints are within distance r.

Hints

Hint 1

Model the points as vertices in an undirected graph and compare squared Euclidean distances against r^2 to avoid floating-point precision issues.

Hint 2

Use Disjoint Set Union (DSU) or standard BFS/DFS graph traversal to count the number of connected components.

Hint 3

For duplicate coordinates, their pairwise distance is 0, which is always at most r^2 for any r >= 0.

Follow-up questions

  • If the number of points scaled to 100,000 and r was relatively small compared to the plane, how could you avoid the O(n^2) pairwise comparisons using spatial partitioning or grid hashing?
  • How would you adapt the solution if points are streamed one by one in real-time and you need to query the cluster count after each insertion?
  • What would change if each point had its own independent coverage radius r_i, creating directed connections rather than undirected ones?