Count Connected Point Clusters
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Google reported this one in July 2026, and the detail that matters is in Example 3: two points at identical coordinates with r = 0 still merge into one cluster. That's the kind of edge case that burns people. The task is counting connected components over up to 2000 points, where two points link if their Euclidean distance is at most r. It's a graph problem dressed as geometry. The candidate who reported it called it the hardest of the coding round, mostly because they overthought it. If you blank on the live OA, StealthCoder runs invisibly on your desktop and hands you the approach in real time.
The problem
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 = 5 return = 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 = 3 return = 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 = 0 return = 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
Reported by candidates. Source: FastPrep
Pattern and pitfall
Treat each point index as a node. Add an edge when the distance is at most r, then count components with Union-Find or DFS. With n up to 2000, the O(n^2) pairwise check is about 2 million comparisons, which is fine. The interviewer in the report preferred brute force over a spatial grid, so don't burn time on fancy neighbor search. The pitfalls are numeric. Coordinates reach 10^9, so dx squared plus dy squared hits about 8 x 10^18. That's close to the signed 64-bit limit, so use long and compare squared distances to r squared. Never use sqrt or floating point, since the boundary case of exactly r must count. Duplicates are separate indices, not deduplicated. Start with count = n and decrement on each successful union. StealthCoder is the hedge if the overflow detail slips your mind mid-assessment.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Count Connected Point Clusters cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Count Connected Point Clusters FAQ
What's the trick to Count Connected Point Clusters?+
It's connected components. Build an implicit graph where points within distance r are linked, then count components with Union-Find or DFS. Start the count at n and subtract one for each union that merges two different roots. Everything else is careful distance math.
Do I need a spatial grid or k-d tree for 2000 points?+
No. Pairwise comparison is roughly 2 million checks at n = 2000, which is fast enough. The interviewer in the original report preferred brute force after the candidate raised optimizations. Mention the grid idea briefly if asked, but code the simple version first.
How do I avoid overflow and precision bugs?+
Compare squared distances. Compute dx*dx + dy*dy as a 64-bit integer and check it against r*r. Coordinates up to 10^9 make dx up to 2*10^9, so squared values are huge. Skip sqrt entirely so points exactly at distance r are included correctly.
How do duplicate points and r = 0 behave?+
Duplicates are separate indices with distance 0, so they connect whenever r >= 0. In Example 3, two points at (1,1) with r = 0 form one cluster, and (2,2) is its own, giving 2. Don't deduplicate or special-case anything. The general check handles it.
How should I prepare in 48 hours for this?+
Write Union-Find with path compression once from memory, then solve this problem end to end. Test the three examples, especially the duplicate case and the exactly-r boundary case. Also be ready to explain DFS or BFS as an alternative. That covers nearly every variant of this question.