Kth Largest Element in a Stream

PracticeNeetCode ↗LeetCode ↗

Design a class that keeps track of the kth largest element in a growing stream of numbers. It's initialized with an integer k and a starting list of numbers, and supports adding one new number at a time, returning the current kth largest value after each add.

Example

Key Pointers

• You never need the full sorted stream — only a min-heap of the k largest values seen so far.
• Once that heap has more than k elements, its smallest member can never be the answer, so pop it.
• The heap's root is always the kth largest, because it's the smallest of the top-k group.

Step-by-Step Analysis

1. On init, heapify the starting nums into a min-heap, then pop down until only k elements remain.
2. On add(val): push val onto the heap.
3. If the heap now holds more than k elements, pop the smallest.
4. Return the heap's root — the current kth largest.

Complexity

Time: O(log k) per add — Space: O(k)

Code

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]

Code Explanation

How the solution above works, piece by piece.

1. Keep a min-heap of size k holding the k largest values seen so far.
2. Its smallest element, heap[0], is then exactly the k-th largest overall.
3. __init__: heapify the starting numbers and pop until only k remain.
4. add: push the new value; if the heap grows past k, pop the smallest (it can no longer be in the top k). Return heap[0].
5. Each add is O(log k); memory is O(k) no matter how long the stream is.

Visual Walkthrough

Running it on k = 3, nums = [4, 5, 8, 2], then add(3), add(5), add(10):

Video Explanation

NeetCode — LeetCode 703