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.
def kClosest(points, k):
return sorted(points, key=lambda x:
x[0]**2 + x[1]**2)[:k]Follow-up:
What if the points are in 3D space?
