Why it works
- After each step the heap holds the k largest numbers read so far: whenever there are k + 1, the smallest of them is popped, and it cannot be among the k largest.
- At the end the heap holds the k largest of the whole array. The smallest of them, the root, is the k-th largest.
- Each copy of a number is pushed on its own, so the two 9s take two places, and the answer is 7, as sorting would give.
Complexity
Time O(n log k): n pushes and at most n pops, each on a heap of at most k + 1 numbers. Memory O(k) for the heap.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗