Lesson 192
Two Heaps Pattern
Running Median in O(log n)
1:00How to maintain a running median in O(log n) per insert by splitting data between a max-heap (smaller half) and a min-heap (larger half).
By the end, you can
- Explain why splitting data into two heaps gives O(1) median queries.
- State the invariant (`maxTop <= minTop`) and describe which heap holds which half.
- Trace the three-step insert algorithm (push to max-heap, transfer max to min-heap, rebalance) on a short stream.
- Hand-compute the running median after each insertion for a small stream.
- Identify when a count is odd vs. even and apply the correct median formula (single root vs. average of roots).
- State the time complexity of addNum and findMedian and explain why they are O(log n) and O(1) respectively.
- Describe the negation trick for simulating a max-heap in Python's min-heap-only `heapq`.
- Recognize problem types (running median, sliding-window median, balanced partition) that call for the two-heaps pattern.
Up next in Coding Interview Patterns
