easy

Kth Largest Element in a Stream

Design a class that finds the kth largest element in a growing stream of numbers.

1. Define the problem

Kth Largest Element in a Stream

You are given an integer k and an initial array of integers nums. You then receive a stream of additional integers, one at a time. After each new value arrives, report the kth largest element seen so far (counting duplicates). Keep a min-heap of exactly k elements — the k largest values seen so far. Its root is always the smallest of those k , so a new value only matters if it beats the root: swap it in and let the heap re-settle.

Constraints

  • 1 ≤ k ≤ 104
  • 0 ≤ nums.length ≤ 104
  • -104 ≤ numsi ≤ 104
  • -104 ≤ val ≤ 104
  • At least k elements exist in the array when you search for the kth element

Example

Inputk = 3, nums = [4, 5, 8, 2], stream = [3, 5, 10, 9, 4]
Output[4, 5, 5, 8, 8]

Explanation The 3 largest of [4, 5, 8, 2] are {4, 5, 8}, root 4. Each stream value either beats the root and replaces it, or is discarded — the root after each step is the answer.

2. Know the words first

In plain terms

Min-heap of size k
A heap capped at k elements holding the k largest values seen so far. Its root is the smallest of the k — the first one to get evicted.
3. Visualize the solution

Keep only the k largest, root is the answer

Keep only the k largest, root is the answer
Statusinit

Initial heap built from [4, 5, 8, 2]: the 3 largest are 4, 5, 8 — root is the smallest of those, 4.

What happens in this step

push 4, 5, 8 one at a time (k = 3)
heap (array) = [4, 5, 8]

each new value settles above its parent without any swaps needed. The 4th value, 2, arrives once the heap is full — since 2 is not greater than root 4, it never enters the heap.
Step 1 of 4

Steps to visualize

  1. Build a min-heap from the k largest values in the initial array.
  2. For each new value, compare it against the heap root (the smallest of the current top k).
  3. If the new value is bigger than the root, swap it in and sift down to restore the invariant.
  4. Otherwise discard it — it is not one of the top k.
  5. The root after each step is the kth largest value seen so far.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Keep only the k largest, root is the answer
Statusinit

Initial heap built from [4, 5, 8, 2]: the 3 largest are 4, 5, 8 — root is the smallest of those, 4.

What happens in this step

push 4, 5, 8 one at a time (k = 3)
heap (array) = [4, 5, 8]

each new value settles above its parent without any swaps needed. The 4th value, 2, arrives once the heap is full — since 2 is not greater than root 4, it never enters the heap.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function kthLargestStream(k, nums, stream) {
  const heap = [];

  function push(val) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent] > heap[i]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function replaceRoot(val) {
    heap[0] = val;
    let i = 0;
    const size = heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left] < heap[smallest]) smallest = left;
      if (right < size && heap[right] < heap[smallest]) smallest = right;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  }

  for (const num of nums) {
    if (heap.length < k) push(num);
    else if (num > heap[0]) replaceRoot(num);
  }

  const results = [];
  for (const val of stream) {
    if (heap.length < k) push(val);
    else if (val > heap[0]) replaceRoot(val);
    results.push(heap[0]);
  }

  return results;
}
Time
O((n + m) log k)
Space
O(k)
6. Test cases

Test cases

InputExpectedCovers
k = 3, nums = [4, 5, 8, 2], stream = [3, 5, 10, 9, 4][4, 5, 5, 8, 8]example from the docstring
k = 1, nums = [], stream = [5, 3, 8][5, 5, 8]k = 1 behaves like a running maximum
k = 2, nums = [8, 5], stream = [10, 9, 4][8, 9, 9]initial array exactly fills the heap
k = 2, nums = [3, 3], stream = [3, 2, 4][3, 3, 3]duplicate values counted separately, ties do not replace the root
k = 1, nums = [-1], stream = [-2, -3, 0][-1, -1, 0]negative numbers mixed with a positive replacement
k = 2, nums = [1], stream = [2, 3][1, 2]heap still filling up partway through the stream

Keep reading