Kth Largest in a Stream

Problem

Design a structure that tracks the kth largest element in a growing stream of numbers. It's initialized with a starting list and a fixed k, and each time a new number arrives you need to report the current kth largest value.

My notes

Signal

"Maintain the kth largest as values keep arriving" means you never need the full sorted order — only a boundary of size k. That's a min-heap holding exactly the k largest values seen so far; its smallest member is your answer.

Approach

Keep a min-heap capped at size k. On each add, push the new value, then if the heap grows past k, pop the smallest — what remains is always the k largest values seen so far, and the kth largest is the heap's root (heap[0]).

Skeleton

heap = smallest k of the initial stream
def add(val):
    push val
    if len(heap) > k: pop smallest
    return heap[0]

Solution

import heapq

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]

Complexity

O(log k) per add — one push and at most one pop on a heap of size k. O(k) space for the heap.

Pitfalls

Keeping all n values in a sorted structure and re-deriving the kth largest each call works but costs O(log n) or worse per op and O(n) space — capping the heap at size k is what makes this O(log k) and O(k) space.
Forgetting to trim the heap down to size k during __init__ if the initial nums list is longer than k.
Reaching for a max-heap here is backwards — you want quick access to the smallest of the largest k, which is exactly what a size-capped min-heap gives you for free.