Given points on a plane and a number k, return the k points closest to the origin. Distance is the usual straight line distance.
DSA Animator › DSA Revision › Heap / Priority Queue › K Closest Points to Origin
Remember: for the k smallest, use a max heap of size k. Compare squared distances to skip the square root. The video solves K Closest Points to Origin (LeetCode 973, Medium) with the Max Heap of Size K pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive K Closest Points to Origin animation.
Given points on a plane and a number k, return the k points closest to the origin. Distance is the usual straight line distance.
For the points 3 3, 5 minus 1 and minus 2 4, with k equal to 2, the answer is 3 3 and minus 2 4.
Sorting all points by distance takes O of n log n. We only need the k closest ones.
Compare squared distances, x squared plus y squared, so no square root is needed. Keep a max heap of at most k points, ordered by distance. The root is the farthest point among the current k closest. When a new point makes the heap bigger than k, poll the root, because it is the worst candidate.
The squared distances are 18 for 3 3, 26 for 5 minus 1, and 20 for minus 2 4. Push 18, then push 26, and 26 becomes the root of the max heap. Push 20, and now there are three points, which is more than k. Poll the root, 26, so the point 5 minus 1 is dropped. The heap holds 20 and 18, so the answer is 3 3 and minus 2 4.
In code, create a priority queue that compares squared distances in reverse order. Offer every point, and poll whenever the size is greater than k. The heap now holds the answer. It's O of n log k time and O of k space.
Remember: for the k smallest, use a max heap of size k. Compare squared distances to skip the square root.