# Kth Largest Element in a Stream

- **Canonical ID**: `kth-largest-element-in-a-stream`
- **Canonical URL**: https://dsacheatsheet.com/problems/kth-largest-element-in-a-stream
- **Difficulty**: easy
- **Patterns**: Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/kth-largest-element-in-a-stream/

## 1. Core Invariant / The Trick

Maintain a **min-heap** capped at size `k`: elements smaller than the k-th largest are evicted on `heappop`. The root `heap[0]` is always the k-th largest element.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log k)`
- **Space Complexity**: `O(k)`
- **Proof**: Heapifying N initial items and trimming to k takes O(N log k); every subsequent `add(val)` takes O(log k).

## 3. Minimal Idiomatic Code

### Python
```python
class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.h = list(nums)
        heapq.heapify(self.h)
        while len(self.h) > k:
            heapq.heappop(self.h)

    def add(self, val: int) -> int:
        if len(self.h) < self.k:
            heapq.heappush(self.h, val)
        elif val > self.h[0]:
            heapq.heapreplace(self.h, val)
        return self.h[0]
```

### TypeScript
```typescript
export class KthLargest {
  private k: number;
  private h: number[] = [];
  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }
  private push(val: number): void {
    this.h.push(val);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  private pop(): number {
    const top = this.h[0];
    const last = this.h.pop()!;
    if (this.h.length > 0) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
        i = s;
      }
    }
    return top;
  }
  add(val: number): number {
    if (this.h.length < this.k) this.push(val);
    else if (val > this.h[0]) { this.pop(); this.push(val); }
    return this.h[0];
  }
}
```

### C++
```cpp
class KthLargest {
    int k;
    priority_queue<int, vector<int>, greater<int>> pq;
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int val) {
        if ((int)pq.size() < k) pq.push(val);
        else if (val > pq.top()) { pq.pop(); pq.push(val); }
        return pq.top();
    }
};
```

### Java
```java
class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> pq = new PriorityQueue<>();
    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int x : nums) add(x);
    }
    public int add(int val) {
        if (pq.size() < k) pq.offer(val);
        else if (val > pq.peek()) { pq.poll(); pq.offer(val); }
        return pq.peek();
    }
}
```

### Go
```go
type KthLargest struct { k int; h IntMinHeap }
func (kl *KthLargest) Add(val int) int {
    if len(kl.h) < kl.k { heap.Push(&kl.h, val) }
    else if val > kl.h[0] { kl.h[0] = val; heap.Fix(&kl.h, 0) }
    return kl.h[0]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Using a max-heap requires storing all N seen elements and scanning k pops per query.
- Calling `add` when heap size is still `k - 1` must push first before reading `heap[0]`.

### Follow-ups
- Offline static array: Quickselect finds the k-th largest in O(N) expected time without extra memory.