You are given points, a list of points on a plane, each written [x, y], and an integer k.
Return the k points closest to the origin (0, 0), measured by ordinary straight-line distance,
√(x² + y²).
Return the points in any order. The tests make sure the answer is unique: the k-th closest point
is always strictly closer than every point left out. The same point may appear more than once in
points; each copy counts as a separate point.
Example 1
- Input
- points = [[2, -1], [-3, 0], [1, 4]], k = 1
- Output
- [[2, -1]]
[2, -1] is closest.Example 2
- Input
- points = [[0, 5], [4, 4], [-1, -2], [3, -3]], k = 2
- Output
- [[-1, -2], [3, -3]]
[[3, -3], [-1, -2]] is right too.Constraints
- 1 ≤
k≤ length ofpoints≤ 10⁴ - −10⁴ ≤ x, y ≤ 10⁴
Show the pattern
Heap
You want the k smallest distances out of many points, without sorting them all. A max-heap of k points keeps the closest so far and drops the farthest of them whenever a nearer point turns up.
See heap in a visualiserShow the approach
Compare points by squared distance x² + y², which orders them exactly as the real distance does.
Walk through the points keeping a max-heap of the k closest seen so far, the farthest of them on
top. Push each point; if the heap now holds k + 1 points, pop the top, which is farther than the
other k and so can't be in the answer. At the end the heap holds the k closest points.
In Python, heapq is a min-heap, so push (-distance, x, y) to keep the farthest on top.
Time: O(n log k) · Space: O(k)