Why it works
- The heap always holds the k closest points read so far. Its root is the farthest of them, so a new point belongs in it exactly when it is closer than the root.
- This is the card’s k largest turned over: for the k smallest distances the heap keeps the largest on top, the one to drop first.
- x² + y² grows with the distance itself, so comparing squares gives the same order without a square root.
Complexity
Time O(n log k): each of n points costs at most one pop and one push on a heap of k. Memory O(k) for the heap.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗