Kth Largest Element in a Stream

Intuition

Just like finding the kth largest of a static array, the kth largest in a stream is the smallest element among the k largest seen so far. A min-heap capped at size k keeps exactly those k values with their minimum at the root, which is the answer we return after every insertion. Seeding the heap from the initial list applies the same trim-to-k rule, so the structure is consistent from the start. Every subsequent add pushes the new value and, if the heap overflows, pops the smallest — an O(log k) operation. Reading the answer is then just peeking at the root.

Algorithm walkthrough

1. 1In the constructor, create an empty min-heap and insert every value from the initial nums, trimming to size k as you go.
2. 2Trimming means: whenever the heap grows past k elements, pop the root so only the k largest survive.
3. 3For add(val), push val onto the heap.
4. 4If the heap now exceeds size k, pop the smallest element to keep only the k largest.
5. 5The root of the heap is the smallest of the k largest values, i.e. the current kth largest.
6. 6Return that root.

Implementation

import heapq
from typing import List

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums[:]
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]