Kth Largest Element in a Stream

EasyHeap · Top K · Design🧩 Heap & Top-K LeetCode #703 ↗Updated Oct 30, 2026

Problem

Build a class KthLargest(k, nums) that starts with the scores in nums and then receives new scores one at a time. Each call add(val) inserts the score and returns the k-th largest value seen so far (counting duplicates, i.e. k-th in sorted order, not k-th distinct).

Inputk=3, nums=[4,5,8,2]Outputinit

Inputadd 3, 5, 10, 9, 4Output4, 5, 5, 8, 8

0 ≤ nums.length ≤ 10⁴ · 1 ≤ k ≤ nums.length + 1 · -10⁴ ≤ val ≤ 10⁴ · ≤ 10⁴ calls to add

Try it yourself

Java

class KthLargest {
    public KthLargest(int k, int[] nums) {
        
    }

    public int add(int val) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Only the k largest values can ever matter: anything smaller than the current k-th largest is buried forever. Keep exactly those k in a min-heap — its root is the answer.

PatternHeap & Top-K

Instinct "K largest / smallest / closest / most frequent", or "always take the best available next"? Keep a heap - size k for top-K, or a ready-queue for scheduling.

Memory hack Guard the top-K club with a bouncer - a min-heap of size k whose root is the weakest member; anyone stronger kicks them out.

Open the Heap & Top-K guide →

Approaches

Brute ForceList + Sort on Every add

Time O(n log n) per addSpace O(n)

Keep every score in a list. On each add, append, sort, and read index size - k. Correct by definition, but re-sorts an almost-sorted list every time (n = scores seen so far).

Java

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

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

    public int add(int val) {
        list.add(val);
        Collections.sort(list);
        return list.get(list.size() - k);
    }
}

Trivial to write; wasteful re-sorting makes many adds slow.

BetterSorted List + Binary-Search Insert

Time O(n) per addSpace O(n)

Keep the list sorted at all times. Binary search finds the insertion point in O(log n); the insert itself shifts elements, so the cost is O(n). The answer is still list.get(size - k).

Java

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

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int x : nums) list.add(x);
        Collections.sort(list);
    }

    public int add(int val) {
        int lo = 0, hi = list.size(); // first index with value >= val
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (list.get(mid) < val) lo = mid + 1;
            else hi = mid;
        }
        list.add(lo, val);
        return list.get(list.size() - k);
    }
}

No re-sorting, but stores every score and shifting is linear.

OptimalMin-Heap of Size k

Time O(log k) per add (init O(n log k))Space O(k)

A min-heap holds the k largest scores seen. Its root is the smallest of them — exactly the k-th largest. Add the new value, and if the heap grows past k, pop the root: it can never be in the top k again.

Java

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

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

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

Logarithmic adds and memory bounded by k, independent of the stream length.

Pro tip

The constructor may see fewer than k numbers (k = nums.length + 1); the heap simply stays smaller until the first add fills it.

At a glance

Level	Approach	Time	Space
Brute Force	List + Sort on Every add	`O(n log n) per add`	`O(n)`
Better	Sorted List + Binary-Search Insert	`O(n) per add`	`O(n)`
Optimal	Min-Heap of Size k	`O(log k) per add (init O(n log k))`	`O(k)`

Common pitfalls

Using a max-heap of everything — finding the k-th still costs O(k log n) pops.
Trimming to k only in add, not in the constructor — heap stays too big.
Assuming nums has ≥ k elements — it can be empty when k = 1.

Interview tips

Say why the k-th largest is the minimum of the top-k set — hence a min-heap.
State per-operation costs separately for init and add.
Mention the follow-up: k-th smallest → max-heap of size k.

Pattern

Size-k min-heap → maintain the top-k / k-th largest over a stream of values.

My notes saved in this browser