I got you!

# Problem:

Implement `KthLargest` class:

• `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`.
• `int add(int val)` Appends the integer `val` to the stream and returns the element representing the `kth` largest element in the stream.

Example 1:

`Input["KthLargest", "add", "add", "add", "add", "add"][[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]Output[null, 4, 5, 5, 8, 8]ExplanationKthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);kthLargest.add(3);   // return 4kthLargest.add(5);   // return 5kthLargest.add(10);  // return 5kthLargest.add(9);   // return 8kthLargest.add(4);   // return 8`

Constraints:

• `1 <= k <= 104`
• `0 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `-104 <= val <= 104`
• At most `104` 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.

# Solution:

## Explanation —

First, in our constructor, we create two instance variables, self.nums and self.k and assign them the parameters that we were passed.

We then heapify the list that we were given.

Now, we pop elements from the heap until there are only k elements left. This is because we need to return the kth largest number, which is just the smallest element in a minheap of k elements.

Note that in Python, popping means removing the smallest element from the heap. Thus the larger elements remain unbothered.

In the add() method, we first push the new element into our heap, and then we pop an element to keep the heap length equal to k.

However, there is a caveat here. We should only pop from the heap if there are at least k+1 elements in it. We could possibly be given a list of length less than k to start with in the first place.

Finally, we return the root of the heap, which is the min element and also the kth largest element in the stream.

## Time and Space Complexity —

Also, we are using a linear amount of auxiliary space, since even though our heap eventually becomes of size k, we initially heapify the entire list nums.

Thus, if n is the length of the input array nums,

Time Complexity: O(nlogn + mlogk)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

# I don’t have friends:

Connect with me on:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

## More from Palash Sharma

A student of science | palashsharma891@gmail.com | https://github.com/palashsharma891 | https://www.linkedin.com/in/palashsharma891/