FastPrepGroup Sparse Points by Distance Threshold
Problem · Graph

Group Sparse Points by Distance Threshold

Learn this problem
● MediumNuro logoNuroFULLTIMEPHONE SCREEN

Problem statement

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

drafts saved locally
public int[][] groupSparsePoints(int[][] points, int k) {
    // Write your solution here.
}
points[[0,0],[1,1],[10,10],[11,10],[30,30]]
k3
expected[[0,1],[2,3],[4]]
checking account