mediumHeap / Priority QueuePure DSA~25 min
Maintain the Kth Largest Value in a Live Stream
Support a stream of incoming numbers and, after each insertion, report the k-th largest value seen so far.
Problem
Design a class that, initialized with an integer k and an initial array nums, supports an add(val) operation that inserts val into the stream and returns the k-th largest element seen so far.
Input
An integer k, an initial array nums, then a sequence of add(val) calls.
Output
Each add returns the current k-th largest value.
Constraints
- 1 <= k <= 10^4
- 0 <= nums.length <= 10^4
- There are at least k elements present whenever a result is requested.
Examples
Example 1
Input
k = 3, nums = [4,5,8,2]; add(3); add(5); add(10); add(9); add(4)
Output
[4,5,5,8,8]
Each add returns the running 3rd largest.
Example 2
Input
k = 1, nums = []; add(-3); add(-2); add(-4)
Output
[-3,-2,-2]
With k=1 it tracks the running maximum.