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.
class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) -> a[0]*a[0] + a[1]*a[1] - b[0]*b[0] - b[1]*b[1]);
return Arrays.copyOfRange(points, 0, k);
}
}Follow-up:
What if the points are in 3D space?
