LeetCode 973 · Medium · Heap / Priority Queue

K Closest Points to Origin

Given points on a plane and an integer k, return the k points nearest to (0, 0) by straight-line distance, in any order.

O(n + k log n)time
O(n)space
min-heapkeyed by x² + y²

1–10 points [x,y] with −9 ≤ x, y ≤ 9 · 1 ≤ k ≤ number of points

Plane green ring: reaches the farthest pick · nothing unpicked lies strictly inside

minHeap tree shows dist = x² + y²

minHeap list dist in the box, point name below

res

public int[][] kClosest(int[][] points, int k) { List<Entry> list = new ArrayList<>(); for (int[] p : points) { int dist = p[0] * p[0] + p[1] * p[1]; list.add(new Entry(dist, p[0], p[1])); } PriorityQueue<Entry> minHeap = new PriorityQueue<>(list); // heapify int[][] res = new int[k][]; for (int i = 0; i < k; i++) { Entry e = minHeap.poll(); res[i] = new int[] {e.x, e.y}; } return res;}static class Entry implements Comparable<Entry> { final int dist, x, y; Entry(int dist, int x, int y) { this.dist = dist; this.x = x; this.y = y; } public int compareTo(Entry o) { // dist, then x, then y if (dist != o.dist) { return Integer.compare(dist, o.dist); } if (x != o.x) { return Integer.compare(x, o.x); } return Integer.compare(y, o.y); }}
picks left
—
dist, x, y
—
minHeap
[]
res
[]

Why it works

  1. Brute force sorts every point by distance and takes the first k: O(n log n). Fine, but it orders points you never return.
  2. A min-heap orders lazily. Heapify puts the closest point at the root without sorting the rest; each pop hands out the next closest. Invariant: every popped point is at least as close as everything still in the heap, which is the ring on the plane.
  3. Cost: heapify is O(n) (the PriorityQueue(Collection) constructor builds bottom-up; adding the points one by one with offer would cost O(n log n)), and k polls are O(k log n), so O(n + k log n) time and O(n) space for the heap.
  4. Pitfall: compare squared distances. x² + y² keeps everything in integers; sqrt is slower and adds float noise without changing the order.
  5. Follow-up: when n is huge and k small, keep a max-heap of size k (largest dist on top, poll when it grows past k) for O(n log k) time and O(k) space. Quickselect gives O(n) on average.