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.
Worked 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]]
Hints
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.
Solution approach
- 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.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n log k) time; O(k) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗