Given points on a plane and k, return the k points closest to the origin, in any order.
Before you code
This is top k smallest, so the heap direction flips: keep a max-heap of the k closest so far, whose root is the farthest of them and the one a new point must beat.
Hints
- Compare squared distances,
x*x + y*y; the square root doesn't change the order. - In Python, push
(-dist, x, y)to simulate a max-heap. - When the heap exceeds k, pop the farthest.
Production & complexity notes
When solving K closest points to origin on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Top-k and merging streams to reinforce the underlying pattern.
What it practices
Choosing the heap direction for a top-k problem, from Top-k and merging streams.