K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on a 2D plane and an integer k, return the k points that are closest to the origin (0, 0). You may return the answer in any order. The distance between two points on a plane is the Euclidean distance.
Constraints:
- 1 <= k <= points.length <= 10^4
- -10^4 < xi, yi < 10^4
Examples:
Input: [[1,3],[-2,2],[5,8],[0,1]], k = 2
Output: [[0,1],[-2,2]]
Explanation: The output depends on the Euclidean distance from the origin.
Solutions
Sorting
Time: O(n log n)Space: O(n)
This solution uses sorting to find the k closest points to the origin. The sorting key is the Euclidean distance from the origin.
var kClosest = function (points, k) {
return points
.sort((a, b) => a[0] * a[0] + a[1] * a[1] - b[0] * b[0] - b[1] * b[1])
.slice(0, k);
};
Follow-up:
What if the points are in 3D space?
