---
# System prepended metadata

title: LC 703. Kth Largest Element in a Stream
tags: [easy, leedcode, Heap, python]

---

# 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<sup>th</sup></code> largest element in a stream. Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></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<sup>th</sup></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<sup>4</sup></code>
- <code>0 <= nums.length <= 10<sup>4</sup></code>
- <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>
- <code>-10<sup>4</sup> <= val <= 10<sup>4</sup></code>
- At most <code>10<sup>4</sup></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<sup>th</sup></code> element.


## Solution 1 - Heap
```python=
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


