← DSA Atlas
Dedicated problem page · #703

Kth Largest Element in a Stream

EasyHeap and Priority QueueFixed-size min-heap (bounded top-k)Min-heap / priority queue
Solve on LeetCode ↗
703
EasyHeap and Priority QueueMin-heap / priority queueFixed-size min-heap (bounded top-k)

Kth Largest Element in a Stream

Design a class KthLargest that tracks the kth largest value in a stream of numbers (the kth largest overall, not the kth distinct). The constructor receives k and an initial array nums. Each call to add(val) inserts val into the stream and returns the kth largest element seen so far.

Open official problem prompt ↗
In plain English

Answer 'what is the kth largest value so far?' after every insertion into a live stream, without re-sorting each time.

Picture it like this

Think of a leaderboard that only keeps the top k scores. When a new score arrives you add it, then bump off the current lowest of the top k. The lowest survivor is exactly the kth-best score.

Example
Input
KthLargest(3, [4, 5, 8, 2]); then add(3), add(5), add(10), add(9), add(4)
Output
[4, 5, 5, 8, 8]
Why
After each add the 3rd-largest value is reported: with {2,4,5,8,3} it is 4, then {..5} makes it 5, then 10 pushes it to 5, then 9 to 8, then 4 to 8.
Constraints
1 <= k <= 10^40 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4-10^4 <= val <= 10^4At most 10^4 calls to addIt is guaranteed there are at least k elements when add is called
Pattern lesson

See the pattern, then code

Fixed-size min-heap (bounded top-k)
Recognition clue

You must repeatedly report the kth largest on a growing stream, not just once. Re-sorting every call is wasteful, which signals keeping a heap of the k best seen so far.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. The kth largest is simply the smallest element among the k largest. Keep exactly the k biggest values in a min-heap; its root is always the answer, and anything smaller than the root can be discarded immediately.

New words, made simpleKnow these before the algorithm
Min-heap
A binary heap whose root is always the smallest element; push and pop cost O(log size).
Streaming query
A question answered repeatedly as new data arrives, rather than once over a fixed input.
kth largest
The value at rank k counting from the biggest, allowing duplicates (not the kth distinct value).
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Sort on every add

Re-sorting the entire history on every call is far too slow for up to 10^4 adds.

Store all values in a list, sort it, and index the kth from the end each time add is called.

Time O(n log n) per addSpace O(n)
Best choiceSize-k min-heap

Constant-size heap gives fast updates and instant answers.

Keep only the k largest values in a min-heap; the root is the kth largest. Each add pushes and possibly pops one element.

Time O(log k) per addSpace O(k)
The rule we keep true

Invariant

After each operation the heap contains exactly the k largest values seen so far, so heap[0] is the kth largest.

Why this is correct

Reasoning

Any value smaller than the current kth largest can never be the kth largest as more elements arrive, so discarding it is safe. Keeping precisely k elements and evicting the minimum whenever the size exceeds k preserves the set of the k biggest values at all times.

The algorithm in three movesSay these aloud before coding
1Heapify nums into a min-heap and trim it down to size k

heap (size 3) = [4, 5, 8]

2On add, push the new value

add(3): push -> pop 3 -> [4,5,8]

3If the heap now exceeds k elements, pop the smallest

root = 4 -> answer

4Return heap[0], the kth largest

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
41
52
83
1 · Readk=3, nums=[4,5,8,2]
2 · AskWhich three are largest?
3 · Update stateheap trimmed to [4,5,8]
4 · Resultroot 4 ready as answer
Key takeaway

The min-heap holds the three largest values; its root (4) is the 3rd largest.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-9Build and trim

    Heapify the initial numbers, then pop until only the k largest remain so the invariant holds before any add.

  2. 2
    Lines 11-15Insert and evict

    Push the new value; if the heap grew past k, remove the smallest so exactly the k largest survive.

  3. 3
    Lines 16Report

    The root of a min-heap of the k largest values is the kth largest, returned in O(1).

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • nums starts empty and grows only via add
  • nums initially has fewer than k elements (heap fills up over the first few adds)
  • duplicate values that tie at rank k
  • negative values in the stream
!

Common beginner mistakes

  • Using a max-heap and scanning for the kth element, which is O(k) per query instead of O(1)
  • Forgetting to trim the initial nums down to size k in the constructor
  • Confusing kth largest with kth distinct largest — duplicates count here
Check your understanding

Why a min-heap and not a max-heap for tracking the kth largest?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word