All Patterns
Pattern 9
Two Heaps
Maintain a max-heap for the lower half and a min-heap for the upper half of a stream. The median is always at their tops.
Time
O(log n) per insertion
Space
O(n)
Recognize it when
- Find median from data stream
- Problems requiring dynamic "middle" element
- Scheduling with two priority groups
Progress0/3
0 solved0 attempted
Questions — ordered by difficulty
#703Easy
Kth Largest Element in a Stream
Design a class that finds the kth largest element in a stream of numbers.
heapdesigndata-stream
#295Hard
Find Median from Data Stream
Design a data structure that supports adding numbers and finding the median at any time.
heapdesigndata-stream
#480Hard
Sliding Window Median
Find the median of each window of size k as it slides over an array.
heapsliding-window