Show problems as
Classic problem #973MediumArrayMathDivide and ConquerGeometrySortingHeap (Priority Queue)QuickselectK-D Tree

K Closest Points to Origin

Real-world version: Nearest Survey Stakes
Tracked in this browser only
Read K Closest Points to Origin on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstFinding Kth Largest/Smallest · Priority Queues, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nearest_stakes(stakes: list[list[int]], k: int) -> list[list[int]]:
Java
public int[][] nearestStakes(int[][] stakes, int k)

More on the same topics