973. K Closest Points to Origin

Given an array of points on the plane and an integer k, return the k points closest to the origin (Euclidean distance), in any order.

Keep the k closest points seen so far in a max-heap keyed by distance. A new point that is closer than the heap's farthest replaces it.

1function kClosest(points: number[][], k: number): number[][] {
2  const dist = (p: number[]) => p[0] ** 2 + p[1] ** 2;
3  const heap = new MaxPriorityQueue<number[]>(dist);
4  for (const p of points) {
5    heap.enqueue(p);
6    if (heap.size() > k) heap.dequeue();
7  }
8  return heap.toArray();
9}

k = 3

points

(3,3) d²=18

(5,-1) d²=26

(-2,4) d²=20

(1,1) d²=2

(0,-2) d²=4

(4,4) d²=32

max-heap (farthest first)

empty

Empty max-heap.

1 / 0

Space: play/pause · ←/→: step