560. K Nearest to Home
A delivery app has a home depot at the origin (0, 0) of a city grid. The array points lists customer locations as [x, y] pairs; the same location can appear several times. Find the k customers closest to the depot by straight-line distance.
Compare locations by squared distance x*x + y*y; if two have the same squared distance, the one with the smaller x comes first, and if x is also equal, the one with the smaller y comes first. Return exactly k locations, listed in this order from nearest to farthest (repeated locations are listed repeatedly).
The intended solution runs in O(n log k) time and O(k) extra space.
Example 1
- Input:
- points = [[3,4],[1,1],[-2,0],[0,5]], k = 2
- Output:
- [[1,1],[-2,0]]
- Explanation:
Squared distances are 25, 2, 4 and 25, so the two nearest are [1,1] then [-2,0].
Example 2
- Input:
- points = [[0,2],[2,0],[-2,0],[0,-2]], k = 4
- Output:
- [[-2,0],[0,-2],[0,2],[2,0]]
- Explanation:
All four are at squared distance 4, so the tie-break by x then y gives [-2,0], [0,-2], [0,2], [2,0].
Example 3
- Input:
- points = [[5,5],[5,5],[1,0]], k = 2
- Output:
- [[1,0],[5,5]]
- Explanation:
The point [1,0] is nearest, then one copy of the duplicated [5,5].
Constraints
- 1 ≤
k≤points.length≤ 105 - -104 ≤
x,y≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log k)
- Space
- O(k)