Group Sparse Points by Distance Threshold
Reported by candidates from Nuro's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Nuro reported this one in September 2026, and the constraint block is the whole story. Up to 100000 points means an all-pairs distance check is dead on arrival, and the problem tells you why: every bucket of side k plus its eight neighbors holds at most 200 points. That's a grid hash plus union-find problem in disguise. You bucket points by floor(coord / k), check only nearby cells, and merge indices that sit strictly closer than k. If you blank on the setup during the live OA, StealthCoder is the safety net running invisibly on your screen.
The problem
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 = 3 return = [[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 = 2 return = [[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 = 3 return = [[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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is spatial hashing. Map each point to a cell (floor(x/k), floor(y/k)) in a hash table keyed by the pair. Two points closer than k must land in the same cell or one of the eight neighbors, so for each point you only compare against those nine cells. The 200-point cap bounds the work per point. Use union-find on original indices, then collect roots, sort members ascending, and sort groups by first index. Pitfalls: floor division on negative coordinates (use Math.floorDiv or equivalent), the strict less-than (distance exactly k is excluded, see Example 2), duplicates being separate vertices that sit at distance 0, and overflow, so square differences in 64-bit. Empty input returns an empty array. If you freeze on the bucket math or negative floor handling in the live OA, StealthCoder can hand you the full solution while you keep typing.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Group Sparse Points by Distance Threshold cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Nuro's OA.
Nuro reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Group Sparse Points by Distance Threshold FAQ
What's the trick in the Nuro group sparse points problem?+
Grid hashing plus union-find. Bucket each point by floor(x/k) and floor(y/k), then only compare against the same cell and its eight neighbors. The constraint guarantees at most 200 points across those nine cells, so total work stays near linear.
Why can't I just compare every pair of points?+
With up to 100000 points, all pairs is about 5 billion distance checks. That times out. The bucket constraint in the problem is a hint that you're meant to prune candidates spatially instead of brute forcing.
What edge cases break most solutions here?+
Negative coordinates with integer division, which truncates toward zero instead of flooring. Also the strict less-than, since distance exactly k must not connect. Duplicates are separate vertices, and squared differences need 64-bit math. Empty input returns an empty array.
How do I format the output correctly?+
Each group is a list of original indices in ascending order, and the groups are sorted by their first index. Iterate indices 0 to n-1, group by union-find root in a map, and the insertion order already gives sorted groups and sorted members.
How do I prepare for this in 48 hours?+
Write union-find with path compression, then practice a grid-hash neighbor lookup using a pair key like a string or a combined 64-bit value. Test it on Example 2 for the strict threshold and on negative coordinates. That covers nearly everything this problem tests.