572. K Closest Points to Origin
You are given points, a list of n points on the plane where points[i] = [xᵢ, yᵢ], and an integer k. Return the k points that lie closest to the origin (0, 0), measured by ordinary Euclidean distance √(x² + y²).
To make the answer unique, use this canonical ordering everywhere: a point is closer than another if its squared distance x² + y² is smaller; on equal distance, the point with the smaller x is considered closer, and on equal x, the one with the smaller y. Return the k closest points under that ordering, listed from closest to farthest.
Note that comparing squared distances gives the same ranking as comparing real distances — no square roots (or floating point) needed.
Example 1:
Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Explanation: Squared distances: (1, 3) → 1 + 9 = 10, and (−2, 2) → 4 + 4 = 8. The smaller one wins, so the single closest point is (−2, 2).
Example 2:
Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]
Explanation: Squared distances are 18, 26, and 20. The two smallest are 18 and 20, so (3, 3) and (−2, 4) are returned, closest first.
Constraints:
- 1 ≤ k ≤ n ≤ 10⁴
- -10⁴ ≤ x_i, y_i ≤ 10⁴
Hints:
Ranking by distance never needs the square root: x² + y² preserves the order and stays in integers.
Sorting all n points works in O(n log n), but you only need the k best. Keep a max-heap of size k: push each point, and whenever the heap exceeds k, discard its largest element. The heap always holds the k closest seen so far.
For average O(n): quickselect. Partition around a random pivot by the (distance, x, y) key until the first k slots hold exactly the k closest, then sort just those k for output.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: points = [[1, 3], [-2, 2]], k = 1
Expected output: [[-2, 2]]