Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easyquick-select

Kth Largest Element in a Stream

Problem (restated)

Design a structure seeded with an integer array and k. Each add(val) inserts val and returns the current kth largest among all values seen so far.

Intuition

The stream never shrinks, so you only need the largest k values. A min-heap of size k: the root is the kth largest. A new value beats the root iff it is larger; then replace. Quick select is the wrong tool here — it is offline.

Approaches

Min-heap of size k

Unverified

Time O(log k) addSpace O(k)

Idea. Constructor pushes every seed through add. add pushes, pops if size > k, returns peek. If fewer than k values have arrived, the heap still has them all (constraints guarantee k is valid by the time you query).

Walkthrough. k=3, seed [4,5,8,2]. Heap [4,5,8]. add 3 → still 4. add 5 → 5. add 10 → 5. add 9 → 8.

Trade-offs. Streaming top-K is a heap, not a partition. Same size-k min-heap as LC 215, reused across calls.

Solution

export class KthLargest {
  private k: number;
  private heap: number[] = [];

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }

  add(val: number): number {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    if (this.heap.length > this.k) this.heap.shift();
    return this.heap[0]!;
  }
}

export class KthLargest {
  private k: number;
  private heap: number[] = [];

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }

  add(val: number): number {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    if (this.heap.length > this.k) this.heap.shift();
    return this.heap[0]!;
  }
}

Template connection

Streaming top K on the Quick Select page: the heap beats the root. Quick select would rebuild from scratch on every add.

Reflection

A min-heap of size k. Once it grows past k, drop the smallest. The top is the kth largest value seen so far.
Before k inserts the top is not yet the kth largest. The problem only queries after that many adds.
Equal values are distinct entries. k = 1 is the running maximum. Older small values fall off the top.