Kth Largest Element in a Stream
The key idea
You never need the whole sorted stream — only the kth largest. Keep a min-heap holding the k largest values seen so far. Its smallest element (the root) IS the kth largest, and any new value either pushes out the current smallest of those k or is too small to matter.
Problem
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Implement KthLargest:
- KthLargest(int k, int[] nums) initializes the object with the integer k and the stream of integers nums.
- int add(int val) appends the integer val to the stream and returns the element representing the kth largest element in the stream.
Constraints
1 <= k <= 10^40 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4-10^4 <= val <= 10^4- At most
10^4calls will be made toadd. - It is guaranteed that there will be at least
kelements in the array when you search for thekthelement.
Examples
Input: ["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output: [null, 4, 5, 5, 8, 8]
Input: ["KthLargest", "add", "add"]
[[1, []], [-3], [-2]]
Output: [null, -3, -2]
Complexity
Time: O(log k) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM