> [!META]- Inline Metadata > [tags:: #career #concepts/programming/heap] > [project group:: Neetcode 150] > [difficulty:: easy] > [status:: done] > [link:: https://leetcode.com/problems/kth-largest-element-in-a-stream/] > [up:: [[Leetcode MOC]]] ## Problem Design a class to find the `kth` largest element in a stream. Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element. 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]` **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:** - `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 ### Mine #### Python ```python class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.stream = nums heapq.heapify(self.stream) while len(self.stream) > self.k: heapq.heappop(self.stream) def add(self, val: int) -> int: heapq.heappush(self.stream, val) if len(self.stream) > self.k: heapq.heappop(self.stream) return self.stream[0] ``` #### Rust ### LC's ## Things I Learned ## Scratchpad Intuitive approach: sort and then find kth largest. O(log n) but then you have to add and keep it sorted which is O(n). So we need a min heap of size k. Only need k-elements because we aren't removing any elements. So we only need a heap of the size k, and a min heap because the kth largest will be the minimum of the heap of size k. Heap: data structure, add/pop O(log n), can get min of heap in O(1) so while size of heap > k, pop minimum. When adding, add to heap, then pop minimum to get size == k Create the heap with `heapq.heapify()` Pop with `heapq.heappop()` Add with `heapq.heappush(self.minHeap, val)` We only want to pop after adding if len(self.minHeap) > k Return self.minHeap[0] for minimum.