71. K Closest Points to Origin
Choose the input point occurrences closest to the origin using ordinary Euclidean distance. Squared distance is sufficient for comparisons and avoids taking square roots.
Equal-distance ties use the original input index. Repeated coordinates still represent distinct occurrences, and output coordinate rows must not alias input rows.
Example 1
Input
[[1,3],[−2,2],[2,−2],[0,0]], k=2
Output
[[0,0],[−2,2]]
Explanation: Origin wins. The distance-eight tie favors input index 1 over 2.
Example 2
Input
[[MIN,MIN],[MAX,MAX],[MIN,MAX]], k=2
Output
[[MAX,MAX],[MIN,MAX]]
Explanation: MIN/MIN has exact squared distance 9,223,372,036,854,775,808 and is farthest, despite its negative signed-long bit pattern.
Example 3
Input
[[1,1]], k=0
Output
fresh []
Explanation: Validation still checks row shape, while no point is selected.
Constraints
0 <= points.length <= 105points[i].length == 2-231 <= points[i][j] <= 231 - 10 <= k <= points.length
Hints
Hint 1
Squared distance has the same order as distance, but audit its maximum possible value.
Hint 2
Which retained point should be evicted when one more point arrives?
Hint 3
Use exact unsigned squared-distance/index rank, a worst-first heap, and fresh sorted output rows.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Origin and equal-distance index ties
[[1,3],[-2,2],[2,-2],[0,0]]
2
[[0,0],[-2,2]]