LeetCode 973 K Closest Points to Origin - Example and Complexity Analysis

Trace [[3,3], [5,-1], [-2,4]] with k = 2.

Squared distances: [3,3] → 18, [5,-1] → 26, [-2,4] → 20.

Process [3,3] (dist 18): heap = [(18, [3,3])].

Process [5,-1] (dist 26): heap = [(26, [5,-1]), (18, [3,3])]. Max-heap, so 26 is at top.

Process [-2,4] (dist 20): 20 < 26 (heap max). Remove [5,-1], add [-2,4]. Heap = [(20, [-2,4]), (18, [3,3])].

Return [[3,3], [-2,4]] (any order).

$O(n \log k)$ time: process $n$ points, each heap operation is $O(\log k)$. $O(k)$ space for heap.