Kth Largest Element In a Stream

Easy · Heap / Priority Queue

Design a small stream tracker that always knows the k-th largest value among every number it has seen so far. The constructor takes k and an initial list of numbers already inserted into the stream. Each later call to add inserts one more number into the stream and must return the current k-th largest value across all numbers inserted so far, counting duplicates separately. You are guaranteed there are always at least k numbers in the stream whenever add's return value is checked.

Examples

Input:  k = 3, nums = [4,5,8,2], then add(3), add(5), add(10), add(9), add(4)
Output: 4, 5, 5, 8, 8
Why:    After each add the object reports the current 3rd largest value seen so far among all numbers inserted.

Input:  k = 1, nums = [], then add(-3), add(-2), add(-4), add(0), add(4)
Output: -3, -2, -2, 0, 4
Why:    With k=1 the answer is simply the maximum value seen so far after each insertion.

Constraints

1 <= k <= 10^4, 0 <= initial nums.length <= 10^4, -10^4 <= nums[i], val <= 10^4, add is called at least k times over the object's lifetime

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Kth Largest Element In a Stream

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Kth Largest Element In a Stream. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.