703. Kth Largest Element in a Stream

Design a class that returns the kth largest value of a growing stream. KthLargest(k, nums) starts the stream; add(val) appends val and returns the current kth largest. Input is a LeetCode-style list of operations.

Keep only the k largest values in a min-heap. Its smallest element is exactly the kth largest overall; anything smaller can be thrown away.

1class KthLargest {
2  heap = new MinPriorityQueue<number>();
3  constructor(private k: number, nums: number[]) {
4    for (const x of nums) this.add(x);
5  }
6  add(val: number): number {
7    this.heap.enqueue(val);
8    if (this.heap.size() > this.k) this.heap.dequeue();
9    return this.heap.front()!;
10  }
11}

op = KthLargest(3)k = 3

min-heap (smallest first)

empty

output

null

k = 3. Add the initial values.

1 / 0

Space: play/pause · ←/→: step