# LC 703. Kth Largest Element in a Stream

### [Problem link](https://leetcode.com/problems/kth-largest-element-in-a-stream/)

###### tags: `leedcode` `python` `easy` `Heap`

Design a class to find the <code>k^th</code> largest element in a stream. Note that it is the <code>k^th</code> largest element in the sorted order, not the <code>k^th</code> distinct element.

Implement <code>KthLargest</code> class:

- <code>KthLargest(int k, int[] nums)</code> Initializes the object with the integer <code>k</code> and the stream of integers <code>nums</code>.
- <code>int add(int val)</code> Appends the integer <code>val</code> to the stream and returns the element representing the <code>k^th</code> 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]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

**Constraints:**

- <code>1 <= k <= 10⁴</code>
- <code>0 <= nums.length <= 10⁴</code>
- <code>-10⁴ <= nums[i] <= 10⁴</code>
- <code>-10⁴ <= val <= 10⁴</code>
- At most <code>10⁴</code> calls will be made to <code>add</code>.
- It is guaranteed that there will be at least <code>k</code> elements in the array when you search for the <code>k^th</code> element.

## Solution 1 - Heap

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.h = []
        self.k = k

        for num in nums:
            heapq.heappush(self.h, num)
            if len(self.h) > k:
                heapq.heappop(self.h)

    def add(self, val: int) -> int:
        heapq.heappush(self.h, val)
        if len(self.h) > self.k:
            heapq.heappop(self.h)
        
        return self.h[0]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogk) | O(k) |

## Note
x