Two Heaps
LC #703Easy
Kth Largest Element in a Stream
Two Heaps
AmazonGoogleMetaProblem
Design a class that finds the kth largest element in a stream of numbers.
heapdesigndata-stream
Constraints
- ›1 ≤ k ≤ 10⁴
- ›0 ≤ nums.length ≤ 10⁴
- ›-10⁴ ≤ nums[i] ≤ 10⁴
- ›At least k elements will exist before any add call
Example
Input
k = 3, nums = [4,5,8,2], add calls: [3],[5],[10],[9],[4]Output
[4, 5, 5, 8, 8]Why
After each add, return the 3rd largest element in the stream so far