FastPrepCount Connected Point Clusters
Problems/Count Connected Point Clusters

Count Connected Point Clusters

Google logoGoogle● MediumNEW GRADPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Backed by a real Google onsite interview report. Estimated match rate: 85-90% for the core task. The original poster said the interview was completed in the first half of 2026 but did not share the exact interview date. I saw the report on 2026-07-09, so FastPrep uses that date as the last-seen date.

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.

Overview

This is a 2D plane clustering problem: 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. A brute-force approach is acceptable.

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
See Google hiring insights
Saved
class Solution {
    public int countConnectedPointClusters(int[][] points, int r) {
      // write your code here
    }

}
Checking account…