Kth Largest Element in a Stream (LC 703)

Pattern: Top K Elements
Difficulty: Easy
Key Concept: Keep a min-heap of size k so the smallest value in the heap is always the k-th largest in the entire stream seen so far.

Problem Statement

Design a class KthLargest that finds the k-th largest element in a stream of integers.

• Constructor KthLargest(int k, int[] nums) initializes the object with the integer k and the initial elements of the stream nums.
• Method int add(int val) appends val to the stream and returns the element representing the k-th largest value in the stream after including val.

Input / Output

• k: positive integer (you always have at least k elements in the stream after each add, per problem constraints).
• nums: initial array (may have length < k in some variants; the official problem guarantees enough elements after adds).
• add(val): returns the k-th largest among all values seen so far (initial + all previous add calls).

Example (conceptual)

• k = 3, nums = [4, 5, 8, 2] → after setup, 3rd largest is 4.
• After add(3), stream contains 4,5,8,2,3 → 3rd largest is still 4.

---

1. Algorithm & Pseudocode

Optimal idea

1. Use a min-heap (smallest element at the top) with at most k elements.
2. After processing any set of values, the k largest values in the stream sit inside the heap.
3. The smallest among those k is exactly the k-th largest overall → peek().

Pseudocode (optimal)

class KthLargest(k, nums):
    heap = empty min-heap

    for x in nums:
        heap.push(x)
        if heap.size > k:
            heap.popMin()   // remove the smallest of the (k+1) values

    function add(val):
        heap.push(val)
        if heap.size > k:
            heap.popMin()
        return heap.peek()

Brute force idea

1. Keep all numbers in a list (initial nums plus every add).
2. On each add, sort the list descending (or ascending and index from the end).
3. Return the element at position k - 1 in the “largest first” order.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why a heap at all? Sorting the whole stream every time is simple but costs O(m log m) per add if m is the current stream length. A heap capped at k keeps only what you need.
2. Why a min-heap for “k-th largest”? You want the k largest values. If you keep more than k, drop the smallest among them—that is the min-heap poll(). What remains are the k largest.
3. Why is peek() the answer? Among the k largest numbers, the smallest one is ranked exactly k-th when you sort descending (there are k - 1 numbers larger than it inside the heap, and everything outside the heap is ≤ it).
4. Constructor vs add: Same rule: push, then if size > k, remove the minimum. That keeps the invariant after initial values and after every new value.
5. Brute force “why it’s slow”: Sorting repeatedly does redundant work; you only need order information for the top k, not a full sort of all elements every time.

---

3. The Dry Run

Parameters: k = 3, nums = [4, 5, 8, 2], then add(3), add(5), add(10), add(9), add(4).

We trace the optimal min-heap (size ≤ 3). Internal heap order is not fully sorted; we show contents as a multiset and peek() (minimum in heap = k-th largest in stream).

Phase A — Constructor (nums processed in order)

Step	Action	Heap contents (multiset)	Heap size	peek() = 3rd largest
init	—	[]	0	—
1	push 4	{4}	1	—
2	push 5	{4,5}	2	—
3	push 8	{4,5,8}	3	4
4	push 2 → size 4 → poll min	{4,5,8}	3	4

Check: Stream {4,5,8,2} sorted desc: 8,5,4,2 → 3rd largest = 4.

Phase B — add operations

Call	Stream (all values)	After push	Size > 3?	After poll if needed	peek() (return)
add(3)	…,3	{3,4,5,8}	yes → remove min 3	{4,5,8}	4
add(5)	…,5	{4,5,5,8}	yes → remove min 4	{5,5,8}	5
add(10)	…,10	{5,5,8,10}	yes → remove min 5	{5,8,10}	5
add(9)	…,9	{5,8,9,10}	yes → remove min 5	{8,9,10}	8
add(4)	…,4	{4,8,9,10}	yes → remove min 4	{8,9,10}	8

Verification (full sort descending after each add):

• After add(3): 8,5,4,3,2 → 3rd = 4.
• After add(5): 8,5,5,4,3,2 → 3rd = 5.
• After add(10): 10,8,5,5,4,3,2 → 3rd = 5.
• After add(9): 10,9,8,5,5,4,3,2 → 3rd = 8.
• After add(4): 10,9,8,5,5,4,4,3,2 → 3rd = 8.

---

4. Java Solution

Brute Force

import java.util.*;

class KthLargestBrute {
    private final int k;
    private final List<Integer> data = new ArrayList<>();

    public KthLargestBrute(int k, int[] nums) {
        this.k = k;
        for (int x : nums) {
            data.add(x);
        }
    }

    public int add(int val) {
        data.add(val);
        Collections.sort(data, Collections.reverseOrder());
        return data.get(k - 1);
    }
}

• Time: Each add sorts O(m log m) where m is current stream size.
• Space: O(m) for the list.

Optimal

import java.util.PriorityQueue;

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int x : nums) {
            minHeap.offer(x);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

• Time: O(n log k) for constructor (n = nums.length), each add is O(log k).
• Space: O(k) for the heap.

---

5. The “Java vs. Others” Edge

• PriorityQueue is a min-heap by default — ideal for “k largest” (evict the global minimum among your candidates). In C++, std::priority_queue is a max-heap by default, so you either invert comparisons or use a custom comparator / store negatives.
• Python heapq is also a min-heap; the same “size-k + pop smallest” pattern applies.
• API clarity: offer / poll / peek express intent for interview code; add/remove also exist on Queue but poll avoids exceptions on empty (here size is guarded).
• Class design: The object stores k and the heap; add mutates shared state — matches how LeetCode expects an object with persistent stream state.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(m log m) per add	O(m)	m = stream length; simple but does not scale.
Optimal	O(log k) per add; O(n log k) init	O(k)	Min-heap of size k; peek is k-th largest.