Core Insight Keep only candidates that may become the next answer, ordered by the priority that matters.
Common Pitfall Push only meaningful candidates and remove stale entries before trusting the root.
Description
Design a stream where you can find the kth largest element.
Constraints
- Time Complexity:
O(n log k) - Space Complexity:
O(k)
Tags
treedesignbinary-search-treeheapdata-stream
Implementation Plan Translate the invariant into these small, testable moves.
- Choose the priority key.
- Push initial candidates.
- Pop the best valid candidate.
- Add newly eligible candidates and repeat.
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.minHeap, self.k = nums, k
heapq.heapify(self.minHeap)
while len(self.minHeap) > k:
heapq.heappop(self.minHeap)
def add(self, val: int) -> int:
heapq.heappush(self.minHeap, val)
if len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)
return self.minHeap[0]