0255MediumArrayMathDivide and ConquerGeometrySortingHeap (Priority Queue)QuickselectK-D Tree

Nearest Survey Stakes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey crew has driven marker stakes across a flat site. Each stake is recorded as a pair [east, north], its offset in metres from the site benchmark, and either offset may be negative.

Given the array stakes and an integer k, return the k stakes nearest the benchmark measured in a straight line across the ground, ordered nearest first. Each returned stake keeps the [east, north] shape it arrived in.

Ties are settled so the answer is never ambiguous: among stakes the same distance from the benchmark, the smaller east offset comes first, and if the east offsets also match, the smaller north offset comes first. Two stakes may sit at the same spot, and a repeated pair is reported as many times as it was recorded.

Examples

Example 1

Input: stakes = [[3, 0], [2, 2], [-1, -1]], k = 2
Output: [[-1, -1], [2, 2]]

The stake at [-1, -1] stands about 1.41 m from the benchmark and the one at [2, 2] about 2.83 m, while [3, 0] stands 3 m away and is left out.

Example 2

Input: stakes = [[5, 0], [0, -5], [1, 7]], k = 2
Output: [[0, -5], [5, 0]]

The first two stakes both stand 5 m from the benchmark, so the smaller east offset of 0 is reported before the east offset of 5; the stake at [1, 7] is further out.

Example 3

Input: stakes = [[0, 0]], k = 1
Output: [[0, 0]]

The only stake is driven at the benchmark itself, 0 m away.

Constraints

1 <= k <= stakes.length <= 10^4
-10^4 <= east, north <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def nearest_stakes(stakes: list[list[int]], k: int) -> list[list[int]]:

Java

public int[][] nearestStakes(int[][] stakes, int k)

The intended approach

Time O(n log k)Space O(k) for the shortlist, which is also the returned answer

Distances only ever get compared, so rank stakes by the whole-number sum of the squared offsets and skip the square root entirely. Carry a shortlist of at most k stakes in a heap ordered so its top is the furthest stake currently shortlisted; each new stake either fills a free slot or displaces that top when it ranks ahead of it. Sort the shortlist at the end to put the answer in nearest-first order, with the east and north offsets settling ties.

Pythonentry point: nearest_stakes

def nearest_stakes(stakes, k):
    import heapq

    worst_first = []
    for stake in stakes:
        east, north = stake[0], stake[1]
        key = (-(east * east + north * north), -east, -north)
        if len(worst_first) < k:
            heapq.heappush(worst_first, key)
        elif key > worst_first[0]:
            heapq.heappushpop(worst_first, key)
    chosen = sorted(worst_first, reverse=True)
    return [[-key[1], -key[2]] for key in chosen]

The obvious version

Rank every stake by squared distance, then east, then north, and take the first k. O(n log n).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_nearest_stakes(stakes, k):
    ranked = sorted(stakes,
                    key=lambda s: (s[0] * s[0] + s[1] * s[1], s[0], s[1]))
    return [[s[0], s[1]] for s in ranked[:k]]

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in