K closest points to the origin
A map holds some points, and the list points gives each one as a list [x, y]. Given a number k, find the k points that lie nearest to the origin, the point [0, 0].
Measure distance in a straight line: from [x, y] to the origin it is the square root of x2 + y2. Return a list of k points, each one the same [x, y] list it was in points, in any order.
The inputs are chosen so the answer is unique: whenever k is less than the number of points, the kth closest point is strictly closer than the next closest one.
points = [[3, 1], [0, 2], [-1, -1], [2, -2]], k = 2Output[[0, 2], [-1, -1]]The squared distances are 9 + 1 = 10, 0 + 4 = 4, 1 + 1 = 2 and 4 + 4 = 8. The two smallest are 2 and 4.
points = [[4, 4], [-1, 6], [0, 0], [3, -5]], k = 3Output[[3, -5], [4, 4], [0, 0]]The squared distances are 32, 37, 0 and 34, so only [-1, 6] is left out. The origin itself is at distance 0. Any order of the three points is accepted.
points = [[1, 0], [0, 1], [-1, 0], [5, 5]], k = 3Output[[1, 0], [0, 1], [-1, 0]]Three points tie at distance 1, and all three are in the answer, so the tie decides nothing.
1 ≤ k ≤ len(points) ≤ 3 × 104
-104 ≤ x, y ≤ 104
The answer is unique.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.