K Closest Points to Origin
Part of Practice: Top-K Fundamentals
You are given a list of points on a 2D plane, where each point is a pair [x, y], plus an integer k. Return the k points that are closest to the origin (0, 0), measured by straight-line (Euclidean) distance. The set of k closest points is guaranteed to be unique, and you may return them in any order.
There can be up to 10^4 points with coordinates between -10^4 and 10^4, and 1 ≤ k ≤ number of points. A useful fact: comparing squared distances x² + y² gives the same ordering as comparing real distances, so no square roots are needed.
Examples
- Input:
- points = [[1, 3], [-2, 2]], k = 1
- Output:
- [[-2, 2]]
Squared distance of (1, 3) is 1 + 9 = 10; squared distance of (-2, 2) is 4 + 4 = 8. Since 8 < 10, the closest point is (-2, 2).
- Input:
- points = [[3, 3], [5, -1], [-2, 4]], k = 2
- Output:
- [[3, 3], [-2, 4]]
Squared distances are 18, 26, and 20. The two smallest are 18 and 20, so those two points win. [[-2, 4], [3, 3]] would also be accepted.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.