This problem, "LeetCode 703", is a popular interview question because it tests the ability to manage dynamic data efficiently without resorting to repeated sorting.

Brute Force Approach for Kth Largest Element in a Stream

A naive approach is to store all elements in a dynamic array (like a standard List or Vector). Whenever a new element is added via the add method, we append it to the list. To find the $k$-th largest element, we sort the entire list in descending order and return the element at index $k-1$.

Pseudo-code:

text
Class KthLargest:
    List store
    int k

    Constructor(k, nums):
        this.k = k
        this.store = copy(nums)

    add(val):
        store.append(val)
        store.sort(descending)
        return store[k-1]

Complexity Analysis:

• Time Complexity: $O(N \log N)$ per add call, where $N$ is the current number of elements in the stream. If we perform $M$ add operations, the total time complexity approaches $O(M \cdot N \log N)$.
• Space Complexity: $O(N)$ to store all elements.

Why it fails: The sorting operation is expensive. As the stream grows, $N$ increases. With up to $10^4$ calls to add, repeatedly sorting a growing array will result in a Time Limit Exceeded (TLE) error. We need a solution that finds the $k$-th largest element in logarithmic time relative to $k$, rather than linear or log-linear time relative to $N$.

Core Insight for Kth Largest Element in a Stream

The key intuition is to realize that to determine the $k$-th largest element, we do not need to keep track of the smaller elements that fall below the top $k$ threshold. We only need to maintain the "elite" set of the $k$ largest scores.

Within this elite set of $k$ elements, the smallest element is the $k$-th largest element of the entire stream. For example, if $k=3$ and the top 3 scores are $\{100, 90, 85\}$, then $85$ is the 3rd largest score overall.

Therefore, we need a data structure that:

1. Efficiently maintains a collection of $k$ elements.
2. Provides fast access to the minimum element within that collection.
3. Allows efficient insertion of new elements and removal of the minimum element.

A Min-Heap of size $k$ satisfies these requirements. By maintaining a Min-Heap with exactly $k$ elements (the $k$ largest seen so far), the root of the heap (the minimum of the heap) will always correspond to the $k$-th largest element globally.

Visual Description: Imagine the heap as a container with a capacity of $k$. As the stream flows, new numbers attempt to enter the container.

• If the container is not full (size $< k$), the new number is simply added.
• If the container is full (size $= k$), we compare the new number with the "weakest" number in the container (the root).
• If the new number is larger than the root, it is "stronger" and deserves a spot in the top $k$. We eject the root (pop) and insert the new number (push). The heap rebalances to surface the new smallest number among the top $k$.
• If the new number is smaller than or equal to the root, it is not large enough to be in the top $k$, so it is discarded (or effectively never enters the top $k$ set).

Execution Flow

Let's trace k = 3, initial stream [4, 5, 8, 2].

1. Initialization:

   • Push 4: Heap [4]
   • Push 5: Heap [4, 5]
   • Push 8: Heap [4, 5, 8] (Size is 3, limit is 3. Root is 4)
   • Push 2: Heap [2, 4, 8, 5] -> Size 4 > 3. Pop min (2). Heap [4, 5, 8]. Root is 4.
   • Initial state established. Heap contains top 3: {4, 5, 8}.

2. add(3):

   • Push 3: Heap [3, 4, 8, 5]
   • Size 4 > 3. Pop min (3).
   • Heap [4, 5, 8].
   • Return root: 4.

3. add(5):

   • Push 5: Heap [4, 5, 8, 5]
   • Size 4 > 3. Pop min (4).
   • Heap [5, 5, 8].
   • Return root: 5.

4. add(10):

   • Push 10: Heap [5, 5, 8, 10]
   • Size 4 > 3. Pop min (5).
   • Heap [5, 8, 10].
   • Return root: 5.

5. add(9):

   • Push 9: Heap [5, 8, 10, 9]
   • Size 4 > 3. Pop min (5).
   • Heap [8, 9, 10].
   • Return root: 8.

Proof of Correctness

The correctness relies on the properties of the Min-Heap.

• Invariant: The Min-Heap contains exactly the $k$ largest elements from the entire history of the stream.
• Base Case: After initialization, we filtered the array so only the $k$ largest remain.
• Inductive Step: When a new value $x$ arrives:
  • If $x$ is smaller than the current $k$-th largest (the root), it cannot be in the top $k$. If we push it and immediately pop, the smallest element (which is $x$) is removed, leaving the heap state unchanged.
  • If $x$ is larger than the root, it belongs in the top $k$. We push $x$ and pop the old root (the previous $k$-th largest). The new root becomes the new smallest among the updated set of $k$ largest elements.
• Conclusion: The root is always the minimum of the top $k$ elements, which is by definition the $k$-th largest element of the entire stream.

Reference Implementation

C++ Solution for LeetCode 703

cpp
#include <vector>
#include <queue>
#include <functional>

using namespace std;

class KthLargest {
private:
    // Min-heap to store the k largest elements
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int k;

public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        // Initialize heap with existing numbers
        for (int num : nums) {
            add(num);
        }
    }
    
    int add(int val) {
        minHeap.push(val);
        
        // If heap size exceeds k, remove the smallest element
        // This ensures the heap only holds the k largest elements
        if (minHeap.size() > k) {
            minHeap.pop();
        }
        
        // The top of the min-heap is the kth largest element
        return minHeap.top();
    }
};

Java Solution for LeetCode 703

java
import java.util.PriorityQueue;

class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        // Min-heap by default in Java
        this.minHeap = new PriorityQueue<>();
        
        for (int num : nums) {
            add(num);
        }
    }
    
    public int add(int val) {
        minHeap.offer(val);
        
        // Maintain exactly k elements (or fewer if total elements < k)
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        
        return minHeap.peek();
    }
}

Python Solution for LeetCode 703

python
import heapq

class KthLargest:

    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.min_heap = []
        
        # Process initial numbers
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        # Push new value to heap
        heapq.heappush(self.min_heap, val)
        
        # If we have more than k elements, remove the smallest
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
            
        # The smallest of the k largest elements is the answer
        return self.min_heap[0]