Group points by distance threshold
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given **N points** in 2D space, `points[i] = (xi, yi)`, and a distance threshold `k > 0`.
Define an undirected graph where there is an edge between two points `i` and `j` if their **Euclidean distance** is **strictly less than `k`**. A **group** is a connected component of this graph (i.e., grouping is **transitive**: if A is within `k` of B and B is within `k` of C, then A, B, C are in the same group even if A and C are not directly within `k`).
### Task
Return the grouping of points (e.g., the number of groups and/or the list of point indices in each group).
### Follow-up
If `N` is very large and points are very **sparse** (most pairs are far apart), how would you **reduce the number of distance computations** compared to checking all `O(N^2)` pairs?
### Assumptions / constraints (you may state your own)
- `1 <= N <= 2e5`
- Coordinates are integers in a large range (e.g., `[-1e9, 1e9]`).
- Distance is Euclidean: `dist((x1,y1),(x2,y2)) = sqrt((x1-x2)^2 + (y1-y2)^2)`.
Quick Answer: This question evaluates understanding of geometric graph construction and connectivity, computational geometry concepts such as Euclidean distance, and algorithmic scalability for grouping points.
Build connected components where point pairs within Euclidean distance strictly less than k are connected. Return sorted groups of point indices.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([(0,0),(1,0),(5,0),(6,0)], 2)
Expected Output: [[0, 1], [2, 3]]
Explanation: Two connected groups.
Input: ([(0,0),(3,0),(6,0)], 4)
Expected Output: [[0, 1, 2]]
Explanation: Transitive grouping.
Input: ([], 1)
Expected Output: []
Explanation: No points.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.