LeetCode 973 K Closest Points to Origin - Why Naive Fails

Sort all points by distance, take the first k.

Sorting takes $O(n \log n)$. But you only need the k closest, not the full sorted order.

If k is much smaller than n, can you avoid sorting everything?