What is the brute force approach and complexity for Kth Largest Element in a Stream?

Keep every number, sort the whole list on each add, read position k with time complexity O(N log N) and space complexity O(N).

What is the optimal approach and complexity for Kth Largest Element in a Stream?

Keep only the k largest in a min-heap; the top is the kth largest with optimal time complexity O(log k) and space complexity O(k).

How do you identify the pattern for Kth Largest Element in a Stream?

Look for key signals in the prompt: "kth largest" indicates A rank counted from the top. The answer is the smallest of the k largest, so a size-k group is enough.; "a stream, with add(val)" indicates Numbers keep arriving. The answer must be ready after every add, without re-reading old numbers.; "returns the kth largest after each add" indicates Keep a size-k min-heap: one push and at most one pop per add..

Kth Largest Element in a Stream

Easy·LeetCode #703Basic Anchor

LeetCode

Jump:

30-Second Mental ModelHeap — Top K (Streaming / dynamic: min-heap of size k)

Complexity:O(N log N)→O(log k)

Key Insight

Keep a min-heap that holds only the k largest numbers seen so far. On each add, push the value, then pop the smallest if the heap has more than k items. Its top is the smallest of the k largest, which is the kth largest overall.

Core Validity Invariant

The heap always holds exactly the k largest numbers seen so far. That makes its top, the smallest of them, the kth largest in the whole stream.

Problem

Build a class KthLargest that keeps a stream of numbers and can tell you its kth largest value at any moment.

KthLargest(int k, vector<int>& nums) starts the stream with the numbers in nums.
int add(int val) adds val to the stream and returns the kth largest number in the stream now.

"kth largest" means: sort the numbers from biggest to smallest and count down from the top. If a number appears twice, each copy counts as its own number.

Input

The integer k, the starting list nums, and then a series of add(val) calls.

Output

For each add call, the kth largest number after that value is added.

Example 1

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

Output: 4, 5, 5, 8, 8

The stream starts as 8, 5, 4, 2, so the 3rd largest is 4. After add(3) the list is 8, 5, 4, 3, 2 and the 3rd is still 4. After add(5) it is 8, 5, 5, 4, 3, 2, so the 3rd is 5. add(10) gives 10, 8, 5, 5, 4, 3, 2, and the 3rd is 5 again. add(9) pushes it to 8, and add(4) leaves it at 8.

Example 2

Input: k = 1, nums = []; then add(-3), add(-2), add(-7)

Output: -3, -2, -2

With k = 1 the answer is simply the largest number so far. After -3 it is -3. After -2 the largest is -2. Adding -7 does not change it.

Constraints

• 0 ≤ nums.length ≤ 10^4
• 1 ≤ k ≤ nums.length + 1
• −10^4 ≤ nums[i] ≤ 10^4
• −10^4 ≤ val ≤ 10^4
• At most 10^4 calls will be made to add

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The answer is a rank, not a value. If the stream holds 8, 5, 5, 4, which number is the 3rd largest?
2.
If I kept every number and sorted on each add, how much work would one add cost?
3.
Suppose k numbers in the stream are already bigger than some value x. Can x ever be the kth largest after that?
4.
Which heap keeps the smallest item on top, and could that smallest item be the one I throw away?
5.
The question only asks about the kth largest. Do I really need to remember every number to answer it forever?

Brute force approach

Idea

Keep every number in one list. On each add, push the new value, sort the list from biggest to smallest, and return the item at index k − 1.

Thinking process

1
Start with nums = [4, 5, 8, 2] and k = 3. Sorted biggest first: 8, 5, 4, 2. The 3rd item is 4.
2
The simplest correct method is to keep every number, sort them again on each add, and read position k.
3
Check add(3): the list becomes 8, 5, 4, 3, 2 after sorting. Position 3 is still 4, so the answer is 4.
4
The cost is the problem. Each add sorts the whole list again, even though only one position is read.

Code & Implementation

brute.cpp

class KthLargest {
    int k;
    vector<int> all;   // every number seen so far

public:
    KthLargest(int k, vector<int>& nums) : k(k), all(nums) {
        sort(all.begin(), all.end(), greater<int>());
    }

    int add(int val) {
        all.push_back(val);
        // Re-sort the whole stream, biggest first, after every add.
        sort(all.begin(), all.end(), greater<int>());
        // In descending order, the kth largest sits at index k - 1.
        return all[k - 1];
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class KthLargest {
    private int k;
    private List<Integer> all; // every number seen so far

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.all = new ArrayList<>();
        for (int x : nums) {
            all.add(x);
        }
        all.sort(Collections.reverseOrder());
    }

    public int add(int val) {
        all.add(val);
        // Re-sort the whole stream, biggest first, after every add.
        all.sort(Collections.reverseOrder());
        // In descending order, the kth largest sits at index k - 1.
        return all.get(k - 1);
    }
}

from typing import List

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.all = list(nums)  # every number seen so far
        self.all.sort(reverse=True)

    def add(self, val: int) -> int:
        self.all.append(val)
        # Re-sort the whole stream, biggest first, after every add.
        self.all.sort(reverse=True)
        # In descending order, the kth largest sits at index k - 1.
        return self.all[self.k - 1]

export class KthLargest {
    private k: number;
    private all: number[]; // every number seen so far

    constructor(k: number, nums: number[]) {
        this.k = k;
        this.all = [...nums];
        this.all.sort((a, b) => b - a);
    }

    add(val: number): number {
        this.all.push(val);
        // Re-sort the whole stream, biggest first, after every add.
        this.all.sort((a, b) => b - a);
        // In descending order, the kth largest sits at index k - 1.
        return this.all[this.k - 1];
    }
}

Complexity

Time O(N log N)Space O(N)

After N numbers, every add sorts all N of them. With up to 10^4 adds on a growing list, that is far too slow, and the list keeps every small number even though they can never be the answer. This is the cost of each add call.

Optimized approach

Idea

Start from brute force

Brute force keeps every number and re-sorts the whole list on each add, just to read one position.

Find the repeated work

Almost all of the sorted list is never read. Only position k matters, but each add sorts all the numbers, including the small ones at the bottom that can never be the answer.

Define the state — what variables do I need?

heap: Min-heap of the k largest numbers seen so far. Its top is the smallest of them.
k: The rank we want, counted from the largest.

Define validity

The heap always holds exactly the k largest numbers seen so far. That makes its top, the smallest of them, the kth largest in the whole stream.

Define the transitions — when does each pointer move, and why is it safe?

add(val)

heap.push(val)

The new value might belong in the top k, so it has to enter the heap first.

heap.size() > k

heap.pop()

There are now k + 1 candidates. The smallest of them is outside the top k, and it can never come back because numbers are never removed from the stream.

After the push and the optional pop

return heap.top()

The heap holds the k largest, so its smallest item is the kth largest.

What does the current window add to the answer?

Each add returns the top of the heap. The heap changes by at most one push and one pop, so the answer is always up to date.

Code & Implementation

optimal.cpp

class KthLargest {
    int k;
    // Min-heap of the k largest numbers seen so far.
    // Its top is the smallest of them, which is the kth largest overall.
    priority_queue<int, vector<int>, greater<int>> heap;

public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }

    int add(int val) {
        heap.push(val);
        // A (k+1)-th largest number can never climb back into the top k,
        // so throw away the smallest one as soon as there are k + 1 of them.
        if ((int)heap.size() > k) heap.pop();
        return heap.top();
    }
};

import java.util.PriorityQueue;

class KthLargest {
    private int k;
    // Min-heap of the k largest numbers seen so far.
    // Its top is the smallest of them, which is the kth largest overall.
    private PriorityQueue<Integer> heap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.heap = new PriorityQueue<>();
        for (int x : nums) {
            add(x);
        }
    }

    public int add(int val) {
        heap.add(val);
        // A (k+1)-th largest number can never climb back into the top k,
        // so throw away the smallest one as soon as there are k + 1 of them.
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

import heapq
from typing import List

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        # Min-heap of the k largest numbers seen so far.
        # Its top is the smallest of them, which is the kth largest overall.
        self.heap: List[int] = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        # A (k+1)-th largest number can never climb back into the top k,
        # so throw away the smallest one as soon as there are k + 1 of them.
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

class MinHeap {
    private data: number[] = [];

    push(val: number): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): number | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): number | undefined {
        return this.data[0];
    }

    size(): number {
        return this.data.length;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.data[parent] > this.data[idx]) {
                [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.data[left] < this.data[smallest]) smallest = left;
            if (right < len && this.data[right] < this.data[smallest]) smallest = right;
            if (smallest !== idx) {
                [this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export class KthLargest {
    private k: number;
    // Min-heap of the k largest numbers seen so far.
    // Its top is the smallest of them, which is the kth largest overall.
    private heap = new MinHeap();

    constructor(k: number, nums: number[]) {
        this.k = k;
        for (const x of nums) {
            this.add(x);
        }
    }

    add(val: number): number {
        this.heap.push(val);
        // A (k+1)-th largest number can never climb back into the top k,
        // so throw away the smallest one as soon as there are k + 1 of them.
        if (this.heap.size() > this.k) {
            this.heap.pop();
        }
        return this.heap.peek()!;
    }
}

Complexity

Time O(log k)Space O(k)

Each add does one push and at most one pop on a heap of size at most k + 1. Building the heap from nums is one add per number, so the constructor costs O(N log k). This is the cost of each add call.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Keep every number, sort the whole list on each add, read position k	O(N log N)	O(N)
Optimal	Keep only the k largest in a min-heap; the top is the kth largest	O(log k)	O(k)

Why does this belong to this pattern?

Clues in the problem statement

“kth largest”A rank counted from the top. The answer is the smallest of the k largest, so a size-k group is enough.
“a stream, with add(val)”Numbers keep arriving. The answer must be ready after every add, without re-reading old numbers.
“returns the kth largest after each add”Keep a size-k min-heap: one push and at most one pop per add.

Stream of values+answer = kth largest+keep only the best k→Heap — Top K (Streaming / dynamic: min-heap of size k)

The Kth Largest Element in an Array question asks for one answer over a fixed array. This question must answer after every add, so the heap has to stay correct as numbers arrive. The rule that makes it work is throw away the smallest as soon as there are k + 1 numbers. For the k smallest numbers, flip the heap to a max-heap; the same idea applies.

Don't make this mistake

Pattern confusion: keeping every number in the heap

✗ heap.push(val); return heap.top(); // min-heap of ALL numbers

✓ heap.push(val); if ((int)heap.size() > k) heap.pop(); return heap.top();

A min-heap of everything has the overall smallest on top, not the kth largest. On the dry run, after the constructor, the heap holds {2, 4, 5, 8}, so the top is 2. The 3rd largest of 8, 5, 4, 2 is 4, but this version returns 2. After add(3), the heap is {2, 3, 4, 5, 8} and it still returns 2. The heap must be cut back to k.

Using the default max-heap

✗ priority_queue<int> heap; // max-heap

✓ priority_queue<int, vector<int>, greater<int>> heap; // min-heap

A max-heap's top is the largest number. Popping when the size is above k then removes the biggest number and keeps the k smallest. On the dry run, the constructor leaves {2, 4, 5} in the max-heap, so the first answer would be 5 instead of 4.

Popping before pushing

✗ if ((int)heap.size() == k) heap.pop(); heap.push(val);

✓ heap.push(val); if ((int)heap.size() > k) heap.pop();

Popping first removes the smallest of the k numbers before we know whether val is bigger. On add(3) with the heap {4, 5, 8}, the pop-first version removes 4, pushes 3, and returns 3. The correct answer is 4, because 3 is the smallest of the four candidates and must be the one dropped.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track

C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track

Smallest Number in Infinite Set