Kth Largest Element in a Stream

Statement

Given an infinite stream of integers (sorted or unsorted), nums, design a class to find the $k^{th}$ largest element in a stream.

Note: It is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.

The class should have the following functions, inputs, and return values:

• Init(nums, k): It takes an array of integers nums and an integer k and initializes the class object.

• Add(value): It takes one integer value, appends it to the stream, and returns the element representing the $k^{th}$ largest element in the stream.

Constraints:

• $1 \leq k \leq 10^3$
• $0 \leq$ nums.length $\leq 10^3$
• $-10^3 \leq$ nums[i] $\leq 10^3$
• $-10^3 \leq$ value $\leq 10^3$
• At most, $10^3$ calls will be made to add.
• It is guaranteed that there will be at least $k$ elements in the array when you search for the $k^{th}$ element.

Examples