Kth Largest Element in a Stream
Last Updated: April 4, 2026
Understanding the Problem
We need a data structure that can handle a growing collection of numbers and quickly answer "what is the kth largest element right now?" every time a new number arrives. The stream only grows (we never remove elements), and we need to return the answer after each insertion.
Here is the key insight: we don't need to track all elements or maintain a fully sorted list. We only care about the top k elements at any given time. If we can efficiently maintain just the k largest elements, the smallest among them is our answer.
Key Constraints:
1 <= k <= 10^4→ k can be fairly large, so we need an approach that handles this efficiently.0 <= nums.length <= 10^4→ The initial array can be empty, which means the first fewaddcalls might not yet have k elements.- At most
10^4calls toadd→ Combined with nums.length, we could see up to 20,000 total elements. Eachaddcall needs to be fast. -10^4 <= val <= 10^4→ Values can be negative. Don't assume all elements are positive.
Approach 1: Sort Each Time
Intuition
The most straightforward approach: every time add is called, insert the new element into the list, sort the entire list, and return the kth largest element (which is at index n - k after sorting).
This is simple to implement and easy to reason about. You are just maintaining a sorted list and reading off the kth position from the end.
Algorithm
- In the constructor, store the initial array and the value of
k. - When
add(val)is called, appendvalto the list. - Sort the entire list.
- Return the element at index
list.size() - k(the kth largest from the end).
Example Walkthrough
Code
- Time Complexity: O(n log n) per
addcall, where n is the current size of the list. Sorting takes O(n log n), and we do this on every call. - Space Complexity: O(n), where n is the total number of elements added. We store every element we've ever seen.
Sorting the entire list every time works, but we're doing far more work than necessary. We only need the kth largest, not a fully sorted list. What if we maintained just the k largest elements using a data structure that gives us the minimum in O(1)?
Approach 2: Min-Heap of Size K
Intuition
We only care about the k largest elements at any point. If an element is smaller than all of the current top k, it can never be the kth largest, so we can discard it.
A min-heap (priority queue) of size k is the perfect tool for this. The heap's root always holds the smallest element in the heap, which is exactly the kth largest element overall. When a new value arrives, we push it onto the heap and pop the minimum if the heap exceeds size k.
Think of it like a VIP section with exactly k seats. To get in, you need to be bigger than the smallest person currently seated. If you are, the smallest person leaves and you sit down. The bouncer (the heap root) is always the smallest person in VIP, which is the kth largest overall.
The min-heap of size k acts as a filter. At any point, the heap contains exactly the k largest elements from the stream seen so far. Because it's a min-heap, the root (smallest element in the heap) is the kth largest overall. When a new element arrives that is larger than the root, it displaces the current kth largest, and the new root becomes the answer.
Algorithm
- In the constructor, create a min-heap. Add all elements from
numsinto the heap. - While the heap size exceeds k, remove the minimum. This trims the heap to only the k largest elements.
- When
add(val)is called, pushvalonto the heap. - If the heap size exceeds k, pop the minimum.
- Return the heap's root (the kth largest element).
Example Walkthrough
Code
- Time Complexity: O(n log k) for the constructor (adding n initial elements to a heap of size k), and O(log k) per
addcall. Each heap push/pop on a heap of size k takes O(log k). - Space Complexity: O(k). We only store k elements in the heap at any time, regardless of how many total elements have been added.