K Closest Points to Origin
Medium· max-heap· top k
Problem
Given a list of points on a plane and an integer k, return the k points closest to (0, 0) by Euclidean distance. Any order is accepted, and the answer is guaranteed to be unique apart from order.
Examples
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Squared distances are 10 and 8.
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Constraints
- • 1 <= k <= points.length <= 10^4
- • -10^4 <= x, y <= 10^4
Hints & approach
Hint 1
Compare squared distances; the square root is unnecessary.
Hint 2
Keep the k best candidates, evicting the farthest one when a closer point shows up.
Hint 3
That calls for a max-heap keyed on distance.
Approachtry the hints first
Iterate over the points while maintaining a max-heap of size k keyed by x^2 + y^2. Push each point; if the heap grows beyond k, pop the farthest. After processing everything, the heap holds the k closest points. Squared distances keep everything in integers, and quickselect on distance is an O(n) average alternative.
Time O(n log k) · Space O(k)