Easy — Heap | Priority Queue | Data Stream | Design

The Problem

Design a class that efficiently finds the kth largest element in a stream of integers, where new values are continuously added and we need to return the kth largest element after each addition.

Approach

Use a min-heap of size k to maintain the k largest elements seen so far. The root of this min-heap will always be the kth largest element, allowing constant-time retrieval after each insertion.

Time: O(log k) per add operation, O(n log k) for initialization · Space: O(k)

Code

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.min_heap = []
        self.k = k

        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.min_heap, val)

        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)

        return self.min_heap[0]

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment