How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Count Clusters of 2D Points Within a Radius

Quick Overview

This question tests graph traversal skills, specifically identifying connected components among a set of 2D points using distance-based adjacency. It assesses the ability to model a geometric problem as a graph and apply DFS, BFS, or Union-Find, a common evaluation of algorithmic thinking in coding interviews. It also probes awareness of efficiency trade-offs when scaling to large point sets.

Count Clusters of 2D Points Within a Radius

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a set of points on a 2D plane and a clustering radius `r`. Two points are considered **directly connected** if the Euclidean distance between them is less than or equal to `r`. Connectivity is **transitive**: if point A connects to B and B connects to C, then A, B, and C all belong to the same cluster, even if the distance between A and C is greater than `r`. A **cluster** is a maximal group of points that are connected to one another (directly or transitively). A single point with no neighbors within distance `r` forms its own cluster of size 1. Given the list of points and the radius `r`, return the total number of clusters. ### Input - `points`: a list of `n` points, where each point is a pair of numbers `[x, y]` giving its coordinates. - `r`: a non-negative number, the connection radius. Two points `p = [x1, y1]` and `q = [x2, y2]` are directly connected when: $$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \le r$$ To avoid floating-point square roots, you may equivalently compare squared distances: `(x1 - x2)^2 + (y1 - y2)^2 <= r * r`. ### Output - A single integer: the number of distinct clusters (connected components) formed by the points. ### Constraints - `1 <= n <= 10^5` - Coordinates `x, y` are integers (or fixed-precision values) with `-10^9 <= x, y <= 10^9`. - `0 <= r <= 2 * 10^9`. - Points may be duplicated; two identical points have distance `0` and are therefore always in the same cluster. ### Examples **Example 1** ``` points = [[0, 0], [1, 0], [10, 10]] r = 2 ``` Output: `2` Explanation: `[0, 0]` and `[1, 0]` are within distance `2` of each other, so they form one cluster. `[10, 10]` is far from both, so it forms a second cluster on its own. Total: `2`. **Example 2** ``` points = [[0, 0], [3, 0], [6, 0]] r = 3 ``` Output: `1` Explanation: `[0, 0]`–`[3, 0]` are connected (distance `3`) and `[3, 0]`–`[6, 0]` are connected (distance `3`). By transitivity all three points are in one cluster, even though `[0, 0]` and `[6, 0]` are distance `6` apart. **Example 3** ``` points = [[0, 0], [5, 5], [100, 100]] r = 1 ``` Output: `3` Explanation: No two points are within distance `1`, so every point is its own cluster.

Quick Answer: This question tests graph traversal skills, specifically identifying connected components among a set of 2D points using distance-based adjacency. It assesses the ability to model a geometric problem as a graph and apply DFS, BFS, or Union-Find, a common evaluation of algorithmic thinking in coding interviews. It also probes awareness of efficiency trade-offs when scaling to large point sets.

You are given a list of points on a 2D plane and a clustering radius `r`. Two points are **directly connected** when the Euclidean distance between them is at most `r`. Connectivity is **transitive**: if A connects to B and B connects to C, then A, B, and C all belong to the same cluster, even if A and C are farther than `r` apart. A **cluster** is a maximal group of mutually connected points (directly or transitively). A point with no neighbor within distance `r` forms its own cluster of size 1. Return the total number of clusters (connected components). Write a function `countClusters(points, r)` where `points` is a list of `[x, y]` pairs and `r` is a non-negative number. To avoid floating-point square roots, compare squared distances: `(x1 - x2)^2 + (y1 - y2)^2 <= r * r`. Example: `points = [[0,0],[1,0],[10,10]]`, `r = 2` returns `2` — `[0,0]` and `[1,0]` merge, `[10,10]` stands alone.

Constraints

1 <= n <= 10^5
-10^9 <= x, y <= 10^9 (use 64-bit integers for squared distances to avoid overflow)
0 <= r <= 2 * 10^9
Points may be duplicated; identical points have distance 0 and are always in the same cluster
Compare squared distances (dx*dx + dy*dy <= r*r) to avoid floating-point square roots

Examples

Input: ([[0, 0], [1, 0], [10, 10]], 2)

Expected Output: 2

Explanation: [0,0] and [1,0] are within distance 2 and merge; [10,10] is isolated. Two clusters.

Input: ([[0, 0], [3, 0], [6, 0]], 3)

Expected Output: 1

Explanation: [0,0]-[3,0] and [3,0]-[6,0] are each exactly distance 3 apart, so by transitivity all three form one cluster even though [0,0] and [6,0] are distance 6 apart.

Input: ([[0, 0], [5, 5], [100, 100]], 1)

Expected Output: 3

Explanation: No two points are within distance 1, so each point is its own cluster.

Input: ([[5, 5]], 0)

Expected Output: 1

Explanation: A single point always forms exactly one cluster, regardless of r.

Input: ([], 5)

Expected Output: 0

Explanation: No points means no clusters.

Input: ([[2, 2], [2, 2], [9, 9]], 0)

Expected Output: 2

Explanation: The two identical points at [2,2] have distance 0 <= 0 and merge; [9,9] is separate. Even with r=0, duplicates cluster together.

Input: ([[0, 0], [4, 3], [8, 6], [8, 6]], 5)

Expected Output: 1

Explanation: [0,0]-[4,3] and [4,3]-[8,6] are each distance 5; the duplicate [8,6] adds nothing. All four points chain into one cluster.

Input: ([[-1000000000, -1000000000], [1000000000, 1000000000]], 2000000000)

Expected Output: 2

Explanation: The diagonal distance is 2e9 * sqrt(2) which is about 2.83e9 > r = 2e9, so the points do NOT connect. This stresses 64-bit squared-distance arithmetic (~8e18).

Input: ([[0, 0], [1, 1], [2, 2], [10, 10], [11, 11]], 2)

Expected Output: 2

Explanation: The chain [0,0]-[1,1]-[2,2] merges into one cluster and the chain [10,10]-[11,11] into another; the two groups are far apart. Two clusters.

Hints

This is a connected-components problem. Model each point as a node and add an edge between any two points within distance r, then count the components with Union-Find (or BFS/DFS).
Never take a square root. Compare (x1-x2)^2 + (y1-y2)^2 against r*r. With coordinates up to 1e9 and r up to 2e9, both sides can reach ~8e18, so use 64-bit (long / long long) arithmetic to avoid overflow.
Only check each unordered pair once (j starts at i+1). Start the component count at n and decrement on each successful union, or at the end count the roots where find(i) == i.
Duplicates and r = 0 fall out naturally: distance 0 <= r*r whenever r >= 0, so identical points always merge.

Last updated: Jul 1, 2026

Loading coding console...

Quick Overview

Count Clusters of 2D Points Within a Radius

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Constraints

1 <= n <= 10^5
-10^9 <= x, y <= 10^9 (use 64-bit integers for squared distances to avoid overflow)
0 <= r <= 2 * 10^9
Points may be duplicated; identical points have distance 0 and are always in the same cluster
Compare squared distances (dx*dx + dy*dy <= r*r) to avoid floating-point square roots

Examples

Input: ([[0, 0], [1, 0], [10, 10]], 2)

Expected Output: 2

Explanation: [0,0] and [1,0] are within distance 2 and merge; [10,10] is isolated. Two clusters.

Input: ([[0, 0], [3, 0], [6, 0]], 3)

Expected Output: 1

Explanation: [0,0]-[3,0] and [3,0]-[6,0] are each exactly distance 3 apart, so by transitivity all three form one cluster even though [0,0] and [6,0] are distance 6 apart.

Input: ([[0, 0], [5, 5], [100, 100]], 1)

Expected Output: 3

Explanation: No two points are within distance 1, so each point is its own cluster.

Input: ([[5, 5]], 0)

Expected Output: 1

Explanation: A single point always forms exactly one cluster, regardless of r.

Input: ([], 5)

Expected Output: 0

Explanation: No points means no clusters.

Input: ([[2, 2], [2, 2], [9, 9]], 0)

Expected Output: 2

Explanation: The two identical points at [2,2] have distance 0 <= 0 and merge; [9,9] is separate. Even with r=0, duplicates cluster together.

Input: ([[0, 0], [4, 3], [8, 6], [8, 6]], 5)

Expected Output: 1

Explanation: [0,0]-[4,3] and [4,3]-[8,6] are each distance 5; the duplicate [8,6] adds nothing. All four points chain into one cluster.

Input: ([[-1000000000, -1000000000], [1000000000, 1000000000]], 2000000000)

Expected Output: 2

Explanation: The diagonal distance is 2e9 * sqrt(2) which is about 2.83e9 > r = 2e9, so the points do NOT connect. This stresses 64-bit squared-distance arithmetic (~8e18).

Input: ([[0, 0], [1, 1], [2, 2], [10, 10], [11, 11]], 2)

Expected Output: 2

Explanation: The chain [0,0]-[1,1]-[2,2] merges into one cluster and the chain [10,10]-[11,11] into another; the two groups are far apart. Two clusters.

Hints

This is a connected-components problem. Model each point as a node and add an edge between any two points within distance r, then count the components with Union-Find (or BFS/DFS).
Never take a square root. Compare (x1-x2)^2 + (y1-y2)^2 against r*r. With coordinates up to 1e9 and r up to 2e9, both sides can reach ~8e18, so use 64-bit (long / long long) arithmetic to avoid overflow.
Only check each unordered pair once (j starts at i+1). Start the component count at n and decrement on each successful union, or at the end count the roots where find(i) == i.
Duplicates and r = 0 fall out naturally: distance 0 <= r*r whenever r >= 0, so identical points always merge.

Last updated: Jul 1, 2026

Loading coding console...