K Closest Points to Origin

Given points on the 2D plane, return the k points closest to the origin (0, 0) using Euclidean distance.

For this judge, keep the output deterministic: return the chosen points sorted by (squaredDistance, x, y) ascending.

Input / output

• Input: points: int[][], k: int
• Output: int[][]

You may compare squared distances instead of taking square roots because the relative ordering is the same.

Examples

1. points = [[1,3],[-2,2]], k = 1 returns [[-2,2]]. Squared distances are 10 and 8, so [-2,2] is closer.
2. points = [[3,3],[5,-1],[-2,4]], k = 2 returns [[3,3],[-2,4]]. Their squared distances are 18, 26, and 20, so the first and third points are chosen, then sorted by distance.
3. points = [[1,1],[-1,-1],[1,-1]], k = 2 returns [[-1,-1],[1,-1]]. All three points have the same squared distance, so tie-break with x and then y.

Constraints

• 1 <= points.length <= 10^4
• 1 <= k <= points.length
• -10^4 <= x, y <= 10^4

Edge cases

• Distances can tie.
• Negative coordinates are allowed.
• k can equal the number of points.

Target complexity

• Aim for O(n log k) selection plus O(k log k) final ordering.

Hints

1. A max-heap of size k can discard the current farthest selected point whenever a better candidate appears.
2. After the heap finishes, sort the selected k points to satisfy the deterministic output contract.

Follow-up How could quickselect reduce the average selection cost if the output order did not need to be sorted?