The problem
Return the k points closest to the origin (any order). Distance is Euclidean.
Stuck? Reveal hints one at a time
How to approach it
- 1For each point, compute d = x² + y².
- 2Push (d, point) into a max-heap by distance; when size exceeds k, pop the farthest.
- 3The heap’s contents at the end are the answer.
Key insight
For "k closest", the heap is a MAX-heap (evict the worst of the best); for "k largest" it is a MIN-heap — the boundary element always guards entry.
The solution
Watch out for
- sqrt() adds float error and cost for zero benefit — squared distance preserves order.
- Quickselect achieves O(n) average if the interviewer pushes past the heap.