K Closest Points to Origin

Medium#973k largest

You get points on a plane as pairs (x, y) and a number k. Return the k points closest to the origin (0, 0), in any order; the answer is always unique. Our example: (2, 2), (-3, 1), (1, 0), (0, -4), (-1, -2), (3, 3) and k = 3 — the answer is (2, 2), (1, 0) and (-1, -2).

973 K Closest Points to OriginWalkthrough · 1×

Example: (2, 2), (-3, 1), (1, 0), (0, -4), (-1, -2), (3, 3), k = 3. Top row: the points, with d, the squared distance, above each one read; below, the max-heap of d, the point under each d.

2,2-3,11,00,-4-1,-23,3max-heapk = 3
not read yetcurrent pointin the heaproot: the farthest keptdroppedanswer

The heap will keep the 3 closest points, with the farthest of them on top

01/28
restart · back · play · step
Speed
1function kClosest(points, k):
2 heap = empty max-heap // ordered by d
3 for each (x, y) in points:
4 d = x * x + y * y
5 if size of heap < k:
6 push (d, x, y) into heap
7 else if d < max of heap:
8 pop max from heap
9 push (d, x, y) into heap
10 return points in heap
state
x
–
y
–
d
–
heap
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The heap always holds the k closest points read so far. Its root is the farthest of them, so a new point belongs in it exactly when it is closer than the root.
  2. This is the card’s k largest turned over: for the k smallest distances the heap keeps the largest on top, the one to drop first.
  3. x² + y² grows with the distance itself, so comparing squares gives the same order without a square root.

Complexity

Time O(n log k): each of n points costs at most one pop and one push on a heap of k. Memory O(k) for the heap.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.