FastPrep
Problem · Graph

Count Connected Point Clusters

Learn this problem
● MediumGoogleNEW GRADONSITE INTERVIEW
See Google hiring insights

Problem statement

You are given a list of 2D integer points and an integer radius r.

Two point indices i and j are considered directly connected when the Euclidean distance between points[i] and points[j] is at most r.

Connectivity is transitive: if point a is connected to point b, and point b is connected to point c, then all three points belong to the same cluster.

Return the total number of connected clusters among all points.

A cluster contains point indices, so duplicate coordinates still represent separate points. If two duplicate points have distance 0, they are directly connected whenever r >= 0.

Original interview report

The coding round included a 2D plane clustering problem, which the candidate felt was the hardest. Given a set of 2D points and a radius r, two points are considered connected if their distance is at most r. The connection relationship is transitive, and the question asks how many clusters remain in the end.

At its core, this is a connected-components problem. DFS, BFS, or Union-Find can be used. If there are many points, neighbor-search optimization should be considered. The candidate initially discussed optimization ideas with the interviewer, but the interviewer ultimately preferred the brute-force approach.

Function

countConnectedPointClusters(points: int[][], r: int) → int

Examples

Example 1

points = [[0,0],[0,3],[4,0],[10,10]]r = 5return = 2

The first three points are in one cluster: (0,0) is within distance 5 of both (0,3) and (4,0), and (0,3) is also exactly distance 5 from (4,0). The point (10,10) is isolated, so there are 2 clusters.

Example 2

points = [[0,0],[3,0],[6,0],[20,0]]r = 3return = 2

(0,0) is directly connected to (3,0), and (3,0) is directly connected to (6,0). Even though (0,0) and (6,0) are not directly connected, transitivity puts the first three points in one cluster. The last point is separate.

Example 3

points = [[1,1],[1,1],[2,2]]r = 0return = 2

The first two points have identical coordinates, so their distance is 0 and they form one cluster. The third point is at positive distance from them, so it forms a second cluster.

Constraints

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

More Google problems

drafts saved locally
public int countConnectedPointClusters(int[][] points, int r) {
  // write your code here
}
points[[0,0],[0,3],[4,0],[10,10]]
r5
expected2
checking account