Kth largest element in a stream of running integers

Hard

Hold exactly k elements

Problem

Design a class that, as numbers stream in, returns the kth largest element so far after each add.

In simple words

Keep a min-heap of the k biggest seen; its top is the running k-th largest.

The idea

Keep a min-heap capped at size k: push each arriving number and pop whenever the size exceeds k. The root is always the kth largest seen so far, answered in O(1) with O(log k) per insertion.

The trick

Trim to size k after every insertion.
Elements smaller than the root can be discarded immediately.

←→stepspaceplay

1/16

Optimal

timeO(n log k)spaceO(k)

Root = kth largest.

1const h = new MinHeap();2for (const x of nums) {3  h.push(x);4  if (h.size() > k) h.pop();5}6return h.peek();

Memory

k: 2
incoming: —
heap size: —
popped: —

Output

2nd largest: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: k = 2, stream = [10, 20, 11, 70, 50]
Output:: [-1, 10, 11, 20, 50]
Explanation:: The 2nd largest after each new number.

Example 2

Input:: k = 1, stream = [1, 2, 3]
Output:: [1, 2, 3]
Explanation:: Largest so far each time.

Example 3

Input:: k = 3, stream = [5, 5, 5]
Output:: [-1, -1, 5]
Explanation:: Only enough elements at the end.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.