K Closest Points to Origin
MediumHeap · Amazon
You are given an array points where points[i] = [x, y] is a point on the plane, and an integer k. Return the k points that are closest to the origin (0, 0).
Closeness is measured by Euclidean distance sqrt(x^2 + y^2). Because square root preserves order, comparing squared distances x^2 + y^2 gives the same ranking.
- The
kpoints may be returned in any order. - The input is chosen so that the answer is unique: there is never a tie between the
k-th and(k+1)-th closest distances. Ties *within* the answer are possible and do not matter. - If the same point appears more than once, each copy is a separate point.
Example 1
- Input:
- points = [[2, -1], [-3, 1], [0, 4], [1, 1]], k = 2
- Output:
- [[1, 1], [2, -1]]
- Explanation
- The squared distances are 5, 10, 16 and 2. The two smallest are 2 (for
[1, 1]) and 5 (for[2, -1]). Any order of these two points is accepted.
Example 2
- Input:
- points = [[6, 2], [-5, -5], [3, -4], [0, 7]], k = 1
- Output:
- [[3, -4]]
- Explanation
- The squared distances are 40, 50, 25 and 49, so
[3, -4](distance 5) is the closest.
Example 3
- Input:
- points = [[3, 0], [0, -3], [5, 5], [-1, 2]], k = 3
- Output:
- [[-1, 2], [0, -3], [3, 0]]
- Explanation
[-1, 2]has squared distance 5, and[3, 0]and[0, -3]both have 9. Those three beat[5, 5]at 50, so they form the answer.
Constraints
1 <= k <= points.length <= 10^4-10^4 <= x, y <= 10^4