LC 703 — Problem

Design a class KthLargest(k, initial[]) that tracks the k-th largest element in a stream. Each call to add(val) inserts the value and returns the current k-th largest.

Input: k = 3, initial = 4582
add(3): returns 4
add(5): returns 5
add(10): returns 5
add(9): returns 8

Constraints: `1 ≤ k ≤ 10^4` · `-10^4 ≤ val ≤ 10^4` · at least `k + 1` total elements by query time · answer must be returned after every `add`.

Phase 1: Fill the sorted shelf

Here is a stream of numbers arriving one at a time. After each arrival, you owe the caller the 5-th largest so far — before the next number shows up. The obvious shot: keep them in a sorted array and read index n - 5.

Tap each incoming value to drop it into the right slot. The counter under the shelf counts every element the array has to shift right to make room. Watch it climb.

incoming stream
9274111613
sorted shelf (k = 5)shifts this round:
Empty — tap the first incoming number to start the shelf.

The ring marks index n − k — the only slot you ever read.

the code running underneath
1
// Sorted-array baseline — O(n) per add (binary search + shift).
2
add(val) {
3
  let lo = 0, hi = this.arr.length;
4
  while (lo < hi) {
5
    const mid = (lo + hi) >> 1;
6
    if (this.arr[mid] < val) lo = mid + 1;
7
    else hi = mid;
8
  }
9
  this.arr.splice(lo, 0, val);     // O(n) shift — the hot spot
10
  return this.arr[this.arr.length - this.k];
11
}