K Closest Points to Origin
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
