EasyNeetCode150TreeDesignBinary Search TreeHeap (Priority Queue)Binary Search Tree
Kth Largest Element in a Stream
Find kth largest in stream.
Examples
Input
KthLargest(3, [4,5,8,2]); add(3)=8; add(5)=8; add(10)=8; add(9)=8; add(4)=9
Output
8,8,8,8,9
3rd largest updates as stream progresses.
Constraints
- •
1 <= k <= 10^4 - •
0 <= nums.length <= 10^4 - •
-10^4 <= nums[i], val <= 10^4 - •
At most 10^4 calls
Approaches
Add and sort each time.
CodeT: O(n log n) init, O(n) add | S: O(n)
class KthLargest:
def __init__(self, k, nums):
self.k=k; self.pool=sorted(nums)
def add(self, val):
import bisect
bisect.insort(self.pool, val)
return self.pool[-self.k]Keep k largest in min heap.
CodeT: O(log k) add | S: O(k)
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k=k; self.h=nums
heapq.heapify(self.h)
while len(self.h)>k: heapq.heappop(self.h)
def add(self, val):
heapq.heappush(self.h, val)
if len(self.h)>self.k: heapq.heappop(self.h)
return self.h[0]Same approach.
CodeT: O(log k) add | S: O(k)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| List Sort | O(n log n) init, O(n) add | O(n) | Add and sort each time. |
| Min Heap Size K | O(log k) add | O(k) | Keep k largest in min heap. |
| Min Heap Optimized | O(log k) add | O(k) | Same approach. |
List Sort
T: O(n log n) init, O(n) addS: O(n)
Add and sort each time.
Min Heap Size K
T: O(log k) addS: O(k)
Keep k largest in min heap.
Min Heap Optimized
T: O(log k) addS: O(k)
Same approach.
Common Mistakes
Using max heap instead of min heap
Wrong heap size
Not maintaining k elements