Description
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
Examples
Input:
points = [[1,3],[-2,2]], k = 1Output:
[[-2,2]]Explanation:
Distance of (-2,2) is sqrt(8), closest to origin.
Input:
points = [[3,3],[5,-1],[-2,4]], k = 2Output:
[[3,3],[-2,4]]Explanation:
Works with negative numbers.
Input:
points = [[0,3],[4,0],[-1,-1],[2,2]], k = 3Output:
[[0,3],[-1,-1],[2,2]]Explanation:
Calculate distances: [0,3] has distance sqrt(9)=3, [4,0] has distance sqrt(16)=4, [-1,-1] has distance sqrt(2)≈1.41, [2,2] has distance sqrt(8)≈2.83. The 3 closest are [-1,-1], [2,2], and [0,3].
Constraints
- •
1 ≤ k ≤ points.length ≤ 10⁴ - •
-10⁴ ≤ xi, yi ≤ 10⁴