Coding Interview PatternsKth Largest Element in a Stream
EasyTop K Elements
Kth Largest Element in a Stream
Explanation & Solution
Description
Design a system to find the kth largest element in a stream of numbers.
You are given an integer k, an initial array of integers nums, and an array additions representing new numbers added to the stream one at a time. For each addition, return the kth largest element in the stream after that number is added.
Note: The kth largest element is the kth largest in sorted order, not the kth distinct element.
Input:k = 3, nums = [4,5,8,2], additions = [3,5,10,9,4]
0
4
1
5
2
8
3
2
0
3
1
5
2
10
3
9
4
4
Output:[4,5,5,8,8]
0
4
1
5
2
5
3
8
4
8
Explanation:
- Add 3: stream = [2,3,4,5,8], 3rd largest = 4
- Add 5: stream = [2,3,4,5,5,8], 3rd largest = 5
- Add 10: stream = [2,3,4,5,5,8,10], 3rd largest = 5
- Add 9: stream = [2,3,4,5,5,8,9,10], 3rd largest = 8
- Add 4: stream = [2,3,4,4,5,5,8,9,10], 3rd largest = 8
Constraints
1 <= k <= nums.length + 10 <= nums.length <= 10⁴-10⁴ <= nums[i] <= 10⁴1 <= additions.length <= 10⁴-10⁴ <= additions[i] <= 10⁴- It is guaranteed that there will be at least
kelements in the stream when eachaddis called.
Approach
Top K Elements pattern
1. Use a Min-Heap of Size k
- Maintain a min-heap that holds exactly the k largest elements seen so far.
- The root of the min-heap (smallest value in the heap) is always the kth largest element.
2. Initialize the Heap with the Starting Array
- Insert each element from
numsinto the min-heap. - After each insertion, if the heap size exceeds
k, remove the smallest element (heap root). - This ensures the heap never holds more than
kelements.
3. Process Each Addition
- For each value in
additions, push it into the min-heap. - If the heap size exceeds
k, pop the minimum element. - After the push/pop, the heap root (
heap[0]) is the kth largest element — record it.
4. Return the Results
- Collect the kth largest value after each addition into a result array.
- Return the result array.
Key Insight
- By keeping only the top
kelements in a min-heap, the smallest of thosekelements is always the kth largest overall. - New elements smaller than the current kth largest are added and immediately removed, so they don't affect the answer.
Time
**O((n + m) log k)** where `n` is the length of `nums` and `m` is the length of `additions`. Each heap operation is O(log k).Space
O(k) for the heap.Visualization
Input:
[4, 5, 8, 2], k = 3
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps