K Closest Points to Origin

K Closest Points to Origin

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).

The distance between two points on the X-Y plane is the Euclidean distance: sqrt(x^2 + y^2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order).

Examples

Example 1:

Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Explanation:
  Distance of (1, 3) = sqrt(10)
  Distance of (-2, 2) = sqrt(8)
  Since sqrt(8) < sqrt(10), (-2, 2) is closer.

Example 2:

Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]
Explanation: The two closest are (3,3) with distance sqrt(18) and (-2,4) with distance sqrt(20).

Constraints

• 1 <= k <= points.length <= 10^4
• -10^4 <= xi, yi <= 10^4

Expected Complexity

• Time: O(n log k)
• Space: O(k)