Pattern visualizer

K Closest Points to Origin

The insight: you don't need to sort all n points by distance — you only need to know whether each new point beats the WORST of the k you're currently keeping. A max-heap of size k does exactly that: its root is always the farthest of your current k candidates, so a new point only needs one comparison against the root to know if it deserves a spot. Capping the heap at size k — evicting the farthest whenever a closer point arrives — gives O(n log k), cheaper than the O(n log n) a full sort would cost. Animated on: Find the k closest points to origin from a set of n points.

Max-heap of size k

time O(n log k)space O(k)step 1 / 7

(1,3)

[0]

(-2,2)

[1]

(5,8)

[2]

(0,1)

[3]

line 5

Add (1,3) with dist=10 (1²+3²). Heap: [10]. Size 1 ≤ k=2. Keep current element.

Pseudocode

1FUNCTION kClosest(points, k):
2  heap = a max-heap keyed by distance
3  FOR each point p in points:
4    dist = p[0]*p[0] + p[1]*p[1]
5    push p onto the heap with its dist
6    IF heap size > k: pop the farthest (the max)
7  END FOR
8  RETURN the heap
9END FUNCTION

← / → step · space play · Home restart

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap