Practice/Meta/Leetcode 973. K Closest Points to Origin

Leetcode 973. K Closest Points to Origin

CodingMust

Problem

You are given an array of coordinate pairs representing points on a 2D plane, along with an integer k. Your task is to identify and return the k points that are closest to the origin (0, 0).

The distance between a point (x, y) and the origin is calculated using the Euclidean distance formula: sqrt(x² + y²). The returned points can be in any order.

Requirements

1. Return exactly k points from the input array
2. The k points must be those with the smallest Euclidean distances to the origin
3. The order of points in the output does not matter
4. If multiple points have the same distance, any valid combination is acceptable

Constraints

• 1 ≤ k ≤ points.length ≤ 10⁴
• -10⁴ ≤ x, y ≤ 10⁴
• Each point is a pair of integers [x, y]
• Time complexity: Aim for O(n log k) or better
• Space complexity: O(k) for the result, plus any auxiliary data structures

Examples

Example 1:

Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: Distance from [1,3] to origin = sqrt(1² + 3²) = sqrt(10) ≈ 3.16 Distance from [-2,2] to origin = sqrt(4 + 4) = sqrt(8) ≈ 2.83 [-2,2] is closer to the origin.

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The two points with smallest distances are [3,3] (distance ≈ 4.24) and [-2,4] (distance ≈ 4.47). The order in the output doesn't matter.

Example 3:

Input: points = [[1,1],[2,2],[3,3]], k = 3 Output: [[1,1],[2,2],[3,3]] Explanation: When k equals the total number of points, return all points.