Katkat
Back

Count Clusters of 2D Points Within a Radius

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model geometric data as a graph and identify connected components using traversal algorithms or Disjoint Set Union (DSU).

Problem Statement

You are given a list of 2D coordinates representing points on a plane and a float r. Two points are considered 'connected' if the Euclidean distance between them is less than or equal to r. A 'cluster' is defined as a group of points where any point in the group can reach any other point in the group through a sequence of connected points.

Write a function that returns the total number of distinct clusters present in the given set of points.

Function Signature

def count_clusters(points: List[Tuple[float, float]], r: float) -> int:

Constraints

  • 1 <= len(points) <= 1000
  • 0 <= r <= 10^4
  • Coordinates are within [-10^4, 10^4]

Example 1

Input: points = [(0, 0), (1, 0), (5, 5), (6, 5)], r = 1.5 Output: 2 Explanation: (0,0) and (1,0) are distance 1 apart (<= 1.5), forming one cluster. (5,5) and (6,5) are distance 1 apart ( 1.0. Thus, each point is isolated, but (1,1) and (2,2) are also > 1.0 apart. If r were 1.5, all three would be one cluster.

Edge Cases

  • Empty input list: return 0.
  • Single point: return 1.
  • Large r where all points form a single cluster.

Hints

Hint 1

Model the points as nodes in a graph where an edge exists between two nodes if their Euclidean distance is <= r.

Hint 2

You can use Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph starting from each unvisited node.

Hint 3

Alternatively, consider using a Disjoint Set Union (DSU) data structure to merge sets as you iterate through all possible pairs of points.

Follow-up questions

  • What is the time complexity of your current solution, and can you optimize it for very large datasets?
  • How would you modify your solution if the input was a stream of points arriving one by one?
  • If the number of points `N` becomes very large (e.g., 100,000), why is an O(N^2) approach inefficient, and what spatial data structures could help (e.g., k-d trees or grid hashing)?