Kth Largest Element in a Stream

Easy·Tagsheappriority-queuedata-stream

Problem Statement

Given an initial array of integers `nums` and an integer `k`, find the `k`th largest element in the dataset. Then, you are given a stream of new elements represented by an array `appendStream`. For every new element in `appendStream`, add it to the dataset and determine the new `k`th largest element. Return an array containing the `k`th largest element after each individual addition from the `appendStream`. Note: It is the `k`th largest element in the sorted order, not the `k`th distinct element.

Examples

Example 1

Input

k: 3, nums: [4, 5, 8, 2], appendStream: [3, 5, 10, 9, 4]

Output

"[4, 5, 5, 8, 8]"

Why

Initial dataset: [4, 5, 8, 2]. Add 3 -> [2, 3, 4, 5, 8]. The 3rd largest is 4. Add 5 -> [2, 3, 4, 5, 5, 8]. The 3rd largest is 5. Add 10 -> [2, 3, 4, 5, 5, 8, 10]. The 3rd largest is 5. Add 9 -> [2, 3, 4, 5, 5, 8, 9, 10]. The 3rd largest is 8. Add 4 -> [2, 3, 4, 4, 5, 5, 8, 9, 10]. The 3rd largest is 8.

Constraints

•1 <= k <= 10^4
•0 <= nums.length <= 10^4
•1 <= appendStream.length <= 10^4
•It is guaranteed that there will be at least k elements in the dataset when calculating the answer.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

To find the 'largest' elements, you might initially think of sorting the array in descending order. But sorting the entire array every time a new element arrives from the stream is extremely slow.

Hint 2

Instead, what if we only kept track of the top 'K' elements at all times? Any element smaller than the top K elements can be safely ignored.

Hint 3

A Min-Heap is perfect for this. If we maintain a Min-Heap strictly of size K, the absolute smallest element in our 'top K' list will sit right at the top of the heap. This happens to be the exact Kth largest element!

Hint 4

Process the initial array: push elements into the Min-Heap. If the heap size exceeds K, pop the top. Then, do the exact same thing for the stream array, recording the top of the heap after each addition.