_703. Kth Largest Element in a Stream.md

703. Kth Largest Element in a Stream

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

Acceptance Rate : 59.5 %

---

Disclaimer: I don't think this question required a heap, given that it's classified as an Easy. The runtime allotment probably would have allowed plain insertions each time despite the $O(n)$ cost, but this would be the optimal way (using heaps).

Version 1

I used a dual heap to keep track of the values, using the bottom (smallest value) of the larger portion as the k-th value.

Version 2

While cleaning the code up, I generated this version wherein I realized that the 
requireemnts don't have any need for the smaller values, and since we're never 
"deleting" values at any point, we don't actually have to store those values and 
make those calculations. As such, I produced a version without those redundancies.

---

Solutions

• e703 v1 Dual Heap.py
• e703 v2 Removed Redundancy.py

Python

e703 v1 Dual Heap.py

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        nums.sort(reverse=True)
        self.larger = [x for x in nums[:k]]     # min heap
        self.smaller = [-x for x in nums[k:]]   # max heap
        self.k = k

        heapq.heapify(self.smaller)
        heapq.heapify(self.larger)

    def add(self, val: int) -> int:
        if len(self.larger) < self.k :
            heapq.heappush(self.larger, val)
            return self.larger[0]
        if self.larger and val == self.larger[0] :
            return val

        if self.larger and val > self.larger[0] :
            transfer = heapq.heappushpop(self.larger, val)
            heapq.heappush(self.smaller, -transfer)
            return self.larger[0]

        heapq.heappush(self.smaller, -val)
        return self.larger[0]
        


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

e703 v2 Removed Redundancy.py

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.larger = [x for x in sorted(nums, reverse=True)[:k]]     # min heap
        self.k = k
        heapq.heapify(self.larger)

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

        if val == self.larger[0] :
            return val

        if val > self.larger[0] :
            heapq.heappushpop(self.larger, val)

        return self.larger[0]


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