FastPrepGroup Sparse Points by Distance Threshold
Problems/Group Sparse Points by Distance Threshold

Group Sparse Points by Distance Threshold

Nuro logoNuro● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks to group two-dimensional points below a distance threshold with union-find and to optimize for sparse points. This practice preserves that strict boundary and supplies Euclidean distance, canonical group ordering, duplicate handling, and portable sparsity bounds; the judged core task matches the report at about 78%.

You are given an array points of two-dimensional integer coordinates and a positive integer k. Treat every point index as a distinct vertex, including indices with duplicate coordinates.

Two vertices share an undirected edge when the squared Euclidean distance between their points is strictly less than k * k. Vertices belong to the same group when they are connected by one or more edges.

Return every connected group as ascending original indices. Sort the groups by their first index. Return an empty array when points is empty.

Function

groupSparsePoints(points: int[][], k: int) → int[][]

Examples

Example 1

points = [[0,0],[1,1],[10,10],[11,10],[30,30]]k = 3return = [[0,1],[2,3],[4]]

Indices 0 and 1 are closer than 3, as are indices 2 and 3. Index 4 has no neighbor within the threshold.

Example 2

points = [[-1,-1],[-1,-1],[1,-1],[-4,-1]]k = 2return = [[0,1],[2],[3]]

The duplicate coordinates at indices 0 and 1 form one group. Their distance to index 2 is exactly k, so the strict threshold excludes that edge.

Example 3

points = [[0,0],[2,0],[4,0],[20,0]]k = 3return = [[0,1,2],[3]]

Indices 0 and 2 are not direct neighbors, but both connect through index 1, so transitivity puts all three in one group.

Constraints

  • 0 <= points.length <= 100000.
  • Every point contains exactly two integers in the range [-1000000000, 1000000000].
  • 1 <= k <= 1000000000.
  • For every occupied grid bucket of side length k, the bucket and its eight neighboring buckets contain at most 200 points in total.
  • Use signed 64-bit arithmetic when squaring coordinate differences.

More Nuro problems

  • Merge Timestamped Record ListsPHONE SCREEN · Seen Oct 2026
  • Assign Robots to Their Nearest Available ItemsPHONE SCREEN · Seen Oct 2026
  • Container With Most WaterPHONE SCREEN · Seen Oct 2026
All Nuro interview questionsSee Nuro hiring insights
Saved
class Solution {
    public int[][] groupSparsePoints(int[][] points, int k) {
        // Write your solution here.
    }
}
Checking account…