K Closest Points to Origin
MediumMax-heap of size k on squared distance
Problem
Return the k points closest to the origin (0,0).
Order points by squared distance (no square root needed) and keep the k nearest with a heap.
The idea
Keep the k closest points in a max-heap ordered by distance, evicting the farthest whenever a closer point arrives. Comparing squared distances avoids the square root entirely, since it preserves the ordering.
The trick
- Compare x² + y²; no need for sqrt.
- O(n log k) time, O(k) space; quickselect averages O(n).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — points=[[1,3],[-2,2]], k=1 Values: 1, 3.
1max-heap of size k by squared distance2for p: push; if size>k pop farthest3return heapInput
- array
- [1, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- points = [[1,3],[-2,2]], k = 1
- Output:
- [[-2, 2]]
- Explanation:
- [-2,2] is nearer the origin.
Example 2
- Input:
- points = [[3,3],[5,-1],[-2,4]], k = 2
- Output:
- [[3, 3], [-2, 4]]
- Explanation:
- The two closest by distance.
Example 3
- Input:
- points = [[0,1]], k = 1
- Output:
- [[0, 1]]
- Explanation:
- Only point.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.