K Closest Points to Origin
The key idea
Rank points by squared distance
x*x + y*y to skip the square root entirely. Keep a max-heap of size k: push each point, and once the heap exceeds k, pop the farthest. Whatever survives is the k closest.Problem
You are given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, and an integer k. Return the k closest points to the origin (0, 0).
The distance between two points is the Euclidean distance: the distance between (x1, y1) and (x2, y2) is the square root of (x1 - x2)^2 + (y1 - y2)^2.
You may return the answer in any order. The answer is guaranteed to be unique (except for the order it is in).
Constraints
1 <= k <= points.length <= 10^4-10^4 <= xi, yi <= 10^4
Examples
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Complexity
Time: O(n log k) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM