Skip to content
DSA Grind
All 26 sections

Kth Largest Element in a Stream (LC 703)

ProblemEasyLeetCode 703Updated
On this page

Pattern: Two Heaps / Size-k Heap
Difficulty: Easy
Key Concept: Keep a min-heap of exactly k largest values seen so far; the heap’s minimum is the kth largest.

Problem Statement

Design a class KthLargest that finds the kth largest element in a stream of integers (elements arrive one at a time).

Constructor
KthLargest(int k, int[] nums)

  • k: which order statistic you want (1 = largest, 2 = second largest, …).
  • nums: initial elements before any add calls.

Method
int add(int val)

  • Appends val to the stream.
  • Returns the current kth largest element after including val.

Constraints (typical)

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i], val <= 10^4
  • At most 10^4 calls to add
  • It is guaranteed that there is always a valid answer when add is called.

Input / Output (conceptual)

  • Input: k, initial nums, then a sequence of add(val) operations.
  • Output: After each add, the kth largest value in all numbers seen so far (initial + all added values).

1. Algorithm & Pseudocode

Brute force (re-sort on every add)

maintain a dynamic list of all values (initial nums + each added val)

on add(val):
  append val to the list
  sort the list in descending order
  return element at index (k - 1)   // 0-based: kth largest

Optimal (min-heap of size k)

use a min-heap pq  // smallest of the k largest sits at the root

helper shrink():
  while pq.size() > k:
    pq.poll()   // drop the smallest among stored candidates

constructor(k, nums):
  store k
  for each x in nums:
    pq.offer(x)
    shrink()
  // pq holds up to k elements: the k largest from nums (if enough elements exist)

add(val):
  pq.offer(val)
  shrink()
  return pq.peek()   // minimum in pq = kth largest overall

Why this works
If you keep exactly the k largest values in a min-heap, the smallest among those k is exactly the kth largest in the full multiset.

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

  1. Why not just sort once?
    New values keep arriving. Any static sort becomes stale after the next add, so you either re-sort (expensive) or maintain a structure that stays correct incrementally.

  2. Why a heap of size k?
    You do not need all n numbers sorted. You only need enough information to know the kth largest. Keeping the top k values is sufficient; anything smaller than the kth largest can be forgotten.

  3. Why a min-heap (not a max-heap)?
    Among the k largest values, the kth largest is the smallest of that group. A min-heap gives you that smallest in O(1) via peek(). If you used a max-heap of size k, the root would be the largest of the stream so far—not what you need.

  4. What does poll() when size > k do?
    After inserting a new value, you might have k + 1 candidates in the heap. Removing the smallest of those k + 1 drops one value that cannot be in the top k, restoring the invariant: heap = k largest elements.

  5. Edge case: fewer than k numbers initially
    Until the stream has at least k elements, the heap may have fewer than k items. Problem statements usually guarantee a valid kth largest by the time answers are required; still, in code you must only call peek() when the heap is non-empty and matches problem guarantees.

  6. Class design
    The constructor sets up k and seeds the heap from nums. Each add updates the structure and returns the answer—encapsulation hides the heap from callers.

3. The Dry Run

Parameters: k = 3, initial nums = [4, 5, 8, 2].

Convention: We use a min-heap; after each batch of operations we show heap contents (as a multiset; order inside the heap tree is not unique). We poll when size exceeds k.

Phase A — Constructor (process initial nums in order)

Step Action Heap contents (multiset) Size After shrink (if > k) peek (3rd largest so far)
A1 offer 4 {4} 1 — 4
A2 offer 5 {4,5} 2 — 4
A3 offer 8 {4,5,8} 3 — 4
A4 offer 2 {2,4,5,8} 4 poll 2 → {4,5,8} 4

After construction, the 3rd largest among [4,5,8,2] is 4.

Phase B — add(3)

Step Action Heap before Size before Heap after offer Size Shrink Heap after Return peek
B1 offer 3 {4,5,8} 3 {3,4,5,8} 4 poll 3 {4,5,8} 4

Phase C — add(5)

Step Action Heap before Offer Size Shrink (poll min) Heap after Return
C1 add 5 {4,5,8} +5 4 poll 4 {5,5,8} 5

(Among {4,5,8,5}, the three largest are 8,5,5; the smallest of those is 5.)

Phase D — add(10)

Step Heap before After offer Size Poll Heap after Return
D1 {5,5,8} {5,5,8,10} 4 poll 5 {5,8,10} 5

Phase E — add(9)

Step Heap before After offer Size Poll Heap after Return
E1 {5,8,10} {5,8,9,10} 4 poll 5 {8,9,10} 8

Phase F — add(4)

Step Heap before After offer Size Poll Heap after Return
F1 {8,9,10} {4,8,9,10} 4 poll 4 {8,9,10} 8

Return value from each add (in order): 4, 5, 5, 8, 8. After construction, peek is 4 before any add; each row above shows the value returned by that add.

4. Java Solution

Brute Force

Idea: Keep an ArrayList, sort descending on every add, return index k - 1.

Time: O(m · (n + m) log(n + m)) over all operations in the worst case (each sort is O(N log N) where N grows with adds). Space: O(n + m) for stored values.

import java.util.*;

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

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

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

Optimal

Time: Each add is O(log k) for heap operations; constructor is O(n log k) for n = nums.length. Space: O(k).

import java.util.PriorityQueue;

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

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

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

5. The “Java vs. Others” Edge

  • PriorityQueue is a min-heap by default in Java—ideal for this pattern. In C++, std::priority_queue is a max-heap by default, so you would use greater or store negated values for the same logic—easy to invert by habit in an interview.
  • Class API: Java’s solution maps cleanly to LeetCode’s KthLargest / add design; fields k and the heap are private, exposing only the contract.
  • No peek on empty: In production you would guard peek(); LeetCode guarantees calls are valid.
  • Alternatives: You could use a fixed-size heap by batching, but the offer + conditional poll pattern is the standard, readable approach.

6. Complexity Summary

Approach Time Space Notes
Brute Force O((n + m) log(n + m)) per add in worst case O(n + m) Re-sorting the full list each time; simple but does not scale.
Optimal O(n log k) init; O(log k) per add O(k) Min-heap of size k; peek gives kth largest.

Here n = nums.length and m is the number of add calls.