K Closest Points to Origin
Max-heap of size k
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.
Details
Animated on: Find the k closest points to origin from a set of n points
Problem:K Closest Points to OriginMedium
Pattern:Heap and Top K
Max-heap of size k
step 1 / 7
Add (1,3) with dist=10 (1²+3²). Heap: [10]. Size 1 ≤ k=2. Keep current element.
- root=0· arr[0] = (1,3)
1FUNCTION kClosest(points, k):2 heap = a max-heap keyed by distance3 FOR each point p in points:4 dist = p[0]*p[0] + p[1]*p[1]5 push p onto the heap with its dist6 IF heap size > k: pop the farthest (the max)7 END FOR8 RETURN the heap9END FUNCTION
← / → step · space play · Home restart
Every step in words
Show all 7 steps
- Add (1,3) with dist=10 (1²+3²). Heap: [10]. Size 1 ≤ k=2. Keep current element.
- Add (-2,2) with dist=8 (2²+(-2)²). Heap: [10, 8]. Size 2 ≤ k=2. Both kept as candidates.
- Add (5,8) with dist=89 (5²+8²). Heap size 3 > k=2. Remove farthest dist=89. Heap reverts to [10, 8] = [(1,3), (-2,2)].
- Add (0,1) with dist=1 (0²+1²). Heap size 3 > k=2. Remove farthest dist=10. Heap: [8, 1] = [(-2,2), (0,1)].
- Heap final state: k=2 closest points with distances 8 and 1. Elements: [(-2,2) dist=8, (0,1) dist=1].
- Final answer: The 2 closest points to origin are [(-2,2), (0,1)]. Their distances from origin are 8 and 1 respectively.
- Animation complete. k=2 closest points identified from 4 points via max-heap. Selected: [(-2,2), (0,1)].
Now solve it yourself
Watching is the first half. The second is writing it without the animation.