Cluster 3D Points by a Distance Threshold
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement `cluster_points_3d(points, D)`.
Create an undirected edge between two distinct 3D points when their Euclidean distance is strictly less than `D`. A cluster is a connected component of this graph, so closeness is transitive through intermediate points.
Return clusters as lists of original point indices. Sort the indices within each cluster, then sort clusters by their smallest index.
### Constraints
- `0 <= len(points) <= 2000`
- Each point is `[x, y, z]` with integer coordinates in `[-10^4, 10^4]`.
- Points are distinct.
- `1 <= D <= 30000`
### Example
For `points = [[0,0,0], [1,0,0], [2,0,0], [10,0,0]]` and `D = 2`, return `[[0,1,2], [3]]`. Points zero and two are connected transitively even though their distance is not less than two.
```hint Test the strict boundary
Two points whose distance is exactly `D` must not be joined.
```
```hint Do not confuse direct closeness with cluster membership
Include a chain where the endpoints are far apart but are connected through intermediate points.
```
Quick Answer: Implement `cluster_points_3d(points, D)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Create an undirected edge between distinct three-dimensional integer points when their Euclidean distance is strictly less than `D`. Return the connected components of that graph as lists of original point indices. Sort indices within each cluster, then sort clusters by their smallest index. Closeness is transitive through intermediate points.
Constraints
- 0 <= len(points) <= 2000, and all points are distinct.
- Every point is [x, y, z] with integer coordinates from -10^4 through 10^4.
- 1 <= D <= 30000; an edge exists only when distance is strictly less than D.
- Indices within each cluster and clusters by smallest index must both be sorted.
Examples
Input: ([], 1)
Expected Output: []
Explanation: Empty input returns no clusters.
Input: ([[0, 0, 0]], 1)
Expected Output: [[0]]
Explanation: A singleton forms one cluster containing index zero.
Hints
- Test empty and singleton inputs, and a pair whose distance is exactly D.
- Include a chain whose endpoints are far apart but connected through intermediate points.
- Use multiple interleaved components to exercise both levels of required output ordering.