Kth Largest Element in a Stream

Given an infinite stream of integers (sorted or unsorted), nums, design a class to find the kth largest element in a stream.

Statement

Given an infinite stream of integers (sorted or unsorted), nums, design a class to find the kth largest element in a stream.

Note: It is the kth largest element in the sorted order, not the kth distinct element.

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

• Init(nums, k) — Takes an array of integers and an integer k, and initializes the class object.
• Add(value) — Takes one integer value, appends it to the stream, and returns the element representing the kth largest element in the stream.

Constraints

• 1 ≤ k ≤ 10³
• 0 ≤ nums.length ≤ 10³
• −10³ ≤ nums[i] ≤ 10³
• −10³ ≤ value ≤ 10³
• At most 10³ 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 kth element.

Examples

Example 1

Input: nums = [4, 6, 8, 7, 5, 9, 4, 2, 3] k = 6

Add(5)

Explanation: After adding 5 to the stream: [4, 6, 8, 7, 5, 9, 4, 2, 3, 5]. Sorting in descending order: [9, 8, 7, 6, 5, 5, 4, 4, 3, 2]. The 6th largest element is 5.

Output: 5

Example 2

Input: nums = [6, 8, 7, 5, 9, 4, 2, 3, 4, 0] k = 6 Add(5)

Explanation: After adding 5 to the stream: [6, 8, 7, 5, 9, 4, 2, 3, 4, 0, 5]. Sorting in descending order: [9, 8, 7, 6, 5, 5, 4, 4, 3, 2, 0]. The 6th largest element is 5.

Output: 5

Example 3

Input:

nums = [6, 8, 7, 5, 9, 4, 2, 3, 4, 0, 3, 0] k = 6 Add(6)

Explanation: After adding 6 to the stream: [6, 8, 7, 5, 9, 4, 2, 3, 4, 0, 3, 0, 6]. Sorting in descending order: [9, 8, 7, 6, 6, 6, 5, 4, 4, 3, 3, 2, 0, 0]. The 6th largest element is 6.

Output: 6

Solution

we'll create a class for kth largest term , in constructor we'll create a heap and call add method for all the numbers.

In add method we'll we'll check size of heap if smaller then k then we'll add but if its not we'll remove peek and add. We do this to maintain k size of heap as in the end we'll have all top kth element

class KthLargest {
    // Constructor to initialize heap and add values in it
        (k, nums) {
        this.topKHeap = new MinHeap();
        this.k = k;

        for (const element of nums) {
            this.add(element);
        }
    }

    // Adds element in the heap and return the Kth largest
    add(val) {
        if (this.topKHeap.size() < this.k) {
            this.topKHeap.offer(val);
        } else if (val > this.topKHeap.peek()) {
            this.topKHeap.poll();
            this.topKHeap.offer(val);
        }

        return this.topKHeap.peek();
    }
}