Given a list of points, where points[i] = [x, y] is a point on the plane, and an integer k, return the k points closest to the origin (0, 0).
The distance between a point [x, y] and the origin is the usual straight-line distance, √(x2 + y2).
Return the points sorted by their distance to the origin, the closest first. Points at the same distance come in order of their x, and points with the same x too in order of their y. The answer is guaranteed to be unique: every point left out is farther from the origin than every point in the answer.
Example 1:
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: [1,3] is √10 away from the origin and [-2,2] is √8 away. √8 is smaller, so [-2,2] is the closest point.
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The squared distances are 18, 26 and 20. The two closest points are [3,3] (18) and [-2,4] (20), in that order.
Example 3:
Input: points = [[0,2],[2,0],[1,1],[0,-2],[3,3]], k = 4 Output: [[1,1],[0,-2],[0,2],[2,0]] Explanation: [1,1] is the closest (√2). [0,2], [2,0] and [0,-2] are all 2 away, so they come by x: [0,-2] and [0,2] (x = 0) before [2,0], and [0,-2] before [0,2] because -2 < 2. [3,3] is the farthest and is left out.
Constraints:
1 <= k <= points.length <= 105-104 <= x, y <= 104- The same point can appear more than once.
- The answer is unique.
Note:
Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the number of points. Sorting all the points by distance would take O(n log n).
No square roots are needed: one point is closer than another exactly when its x2 + y2 is smaller, and that squared distance is a whole number of at most 2 · 108, which fits in a 32-bit integer.
Free plan: 30 tutor messages. PRO is unlimited.
