#973
K Closest Points to Origin
Medium Max-heap of size k
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the k points closest to (0, 0), in any order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k points nearest to (0, 0).
Why this works: a max-heap of size k by distance; when a closer point comes, the farthest of the kept ones leaves.
Example: [[1,3], [-2,2]], k = 1
distances 10 and 8 → keep [-2, 2]✦Hints open one at a time
Compare squared distances — no need for square roots.
Keep a max-heap of the k closest so far; evict the farthest when it grows past k.
↗Approach
Push each point into a max-heap ordered by x² + y². Poll when the size exceeds k. The heap holds the answer.
</>Solution (Java)
import java.util.*;
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a))); // farthest on top
for (int[] p : points) {
heap.offer(p);
if (heap.size() > k) heap.poll();
}
return heap.toArray(new int[0][]);
}
private int dist(int[] p) {
return p[0] * p[0] + p[1] * p[1];
}
}!Common mistake
Using a min-heap of all n points and polling k times — O(n log n), more memory.
Complexity
- Time: O(n log k).
- Space: O(k).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon