Description
Return k points with the smallest squared distance to (0, 0). The point order is irrelevant. Assume 1 <= k <= the point count and the selected set is uniquely determined.
Solution
def k_closest(points, k):
return sorted(points, key=lambda p: p[0] * p[0] + p[1] * p[1])[:k]Examples
Example 1
- Input
[[[1,3],[-2,2]],1]- Output
[[-2,2]]
Distances squared are 10 and 8.
Example 2
- Input
[[[3,3],[5,-1],[-2,4]],2]- Output
[[3,3],[-2,4]]
Squared distances 18 and 20 are the smallest.
Example 3
- Input
[[[0,0]],1]- Output
[[0,0]]
The origin has distance zero.
Approach
Copy and sort the points by x squared plus y squared, then take the first k. Squared distances preserve the order without square roots.
Time & space
O(n log n) time and O(n) auxiliary space, where n is the number of points.