easy

Kth Largest Element in a Stream

Design a class initialized with k and an initial list of scores. Each call to add(val) appends a new score and returns the k-th largest score seen so far.

Constraints

1 ≤ k ≤ 10^4
0 ≤ initial length ≤ 10^4
At most 10^4 calls to add
There are at least k elements whenever add returns

Examples

in: k = 3, nums = [4,5,8,2]; add(3), add(5), add(10), add(9), add(4)

out: 4, 5, 5, 8, 8

Recognition clues

Streaming input — answer must update per insertion
Only the k largest ever matter
A min-heap of size k has the k-th largest at its root

Pattern

Heap / Priority Queue

When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.

Min-Heap Priority Queue Binary Heap

Solution

Maintain a min-heap containing at most k elements: the largest k seen so far. On add, push the value and, if the size exceeds k, pop the minimum. The heap root is then the smallest of the top k, i.e. the k-th largest overall. Each operation is logarithmic in k.

time O(log k) per addspace O(k)

Alternative approaches

Keeping a sorted array and inserting with binary search is O(k) per add due to shifting; a balanced BST with size augmentation is O(log n) but heavier.

Code it yourself

Solve in

Hints:

Learn Binary Heap ▶ Visualize