Kth Largest Element in a Stream

LeetCode 703: Kth Largest Element in a Stream Solution & Explanation

Problem Overview

TL;DR: Maintain a Min-Heap of size exactly $k$ containing the largest elements seen so far; the root of this heap is always the $k$-th largest element.

The problem requires designing a class that processes a continuous stream of test scores. We must initialize the class with an integer $k$ and an initial array of scores. The core functionality is the add method, which accepts a new score and returns the $k$-th largest score among all scores seen up to that point (including the initial set and all subsequent additions). This is a classic example of processing data in a stream where the full dataset changes dynamically.

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:

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$.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Initialization:

   • Create a Min-Heap.
   • Iterate through the initial nums array.
   • Push each number into the Min-Heap.
   • If the heap size exceeds $k$, pop the smallest element (the root). This ensures the heap only holds the largest $k$ elements found so far.

2. Add Operation:

   • Push the new val into the Min-Heap.
   • If the heap size exceeds $k$, pop the root.
   • The root of the heap is now the answer. Return it.

3. Constraint Enforcement:

   • The invariant is that the Min-Heap size never exceeds $k$ (after processing).
   • Note: It is possible for the heap to have fewer than $k$ elements initially if the input array is small. In that case, the problem constraints usually imply we won't be asked for the $k$-th largest until we have at least $k$ elements, or we just return the minimum of what we have.

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.

Pattern Reuse Notes

The "Heap - Top K Elements" pattern is versatile. The logic used in LeetCode 703 applies directly to:

• LeetCode 215: Kth Largest Element in an Array - The static version of this problem.
• LeetCode 347: Top K Frequent Elements - Uses a Min-Heap of size $k$ to track elements with the highest frequencies.
• LeetCode 451: Sort Characters By Frequency - Can use a heap to extract characters in frequency order.
• LeetCode 506: Relative Ranks - Assigns ranks based on sorted order, solvable via heap extraction.

Understanding the invariant of the Min-Heap size allows you to solve almost any "Top K" problem efficiently.

Reference Implementation

C++ Solution for LeetCode 703

1#include <vector>
2#include <queue>
3#include <functional>
4
5using namespace std;
6
7class KthLargest {
8private:
9    // Min-heap to store the k largest elements
10    priority_queue<int, vector<int>, greater<int>> minHeap;
11    int k;
12
13public:
14    KthLargest(int k, vector<int>& nums) {
15        this->k = k;
16        // Initialize heap with existing numbers
17        for (int num : nums) {
18            add(num);
19        }
20    }
21    
22    int add(int val) {
23        minHeap.push(val);
24        
25        // If heap size exceeds k, remove the smallest element
26        // This ensures the heap only holds the k largest elements
27        if (minHeap.size() > k) {
28            minHeap.pop();
29        }
30        
31        // The top of the min-heap is the kth largest element
32        return minHeap.top();
33    }
34};

Java Solution for LeetCode 703

1import java.util.PriorityQueue;
2
3class KthLargest {
4    private PriorityQueue<Integer> minHeap;
5    private int k;
6
7    public KthLargest(int k, int[] nums) {
8        this.k = k;
9        // Min-heap by default in Java
10        this.minHeap = new PriorityQueue<>();
11        
12        for (int num : nums) {
13            add(num);
14        }
15    }
16    
17    public int add(int val) {
18        minHeap.offer(val);
19        
20        // Maintain exactly k elements (or fewer if total elements < k)
21        if (minHeap.size() > k) {
22            minHeap.poll();
23        }
24        
25        return minHeap.peek();
26    }
27}

Python Solution for LeetCode 703

1import heapq
2
3class KthLargest:
4
5    def __init__(self, k: int, nums: list[int]):
6        self.k = k
7        self.min_heap = []
8        
9        # Process initial numbers
10        for num in nums:
11            self.add(num)
12
13    def add(self, val: int) -> int:
14        # Push new value to heap
15        heapq.heappush(self.min_heap, val)
16        
17        # If we have more than k elements, remove the smallest
18        if len(self.min_heap) > self.k:
19            heapq.heappop(self.min_heap)
20            
21        # The smallest of the k largest elements is the answer
22        return self.min_heap[0]