Why it works
- The heap always holds the k largest numbers seen so far. The smallest of them is on top, and that is exactly the k-th largest.
- A number below the root cannot be among the k largest, now or later: numbers only arrive and never leave. So it goes in and is popped at once, as 3 is here.
- The heap never grows past k + 1, so each add costs O(log k) however many numbers came before.
Complexity
init: time O(n log n) for n numbers. Each add: time O(log k), one push and at most one pop. Memory O(k) after init: the heap keeps k numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗