The Two-Heaps Pattern: Finding the Running Median in Coding Interviews

"Find the median of a data stream" is one of the most common hard-level interview questions, and the clean solution uses a pattern worth knowing on its own: two heaps that split the data into a lower half and an upper half. Once you understand why it works, a handful of related problems become straightforward. The problem Numbers arrive one at a time. After each insertion, return the median of everything seen so far. Re-sorting each time costs O(n log n) per query, and inserting into a sorted list is O(n). We want O(log n) per insertion and O(1) per median query. The idea Keep two heaps: - low: a max-heap holding the smaller half of the numbers. - high: a min-heap holding the larger half. Maintain two invariants: every number in low is less than or equal to every number in high, and the sizes differ by at most one (we let low hold the extra element). Then the median is either the top of low (odd count) or the average of both tops (even count). Implementation in Python import heapq class MedianFinder: def __init__(self): self.low = [] # max-heap via negated values self.high = [] # min-heap def add(self, num): heapq.heappush(self.low, -num) # move the largest of low to high to keep ordering heapq.heappush(self.high, -heapq.heappop(self.low)) # rebalance so low has the extra element if len(self.high) > len(self.low): heapq.heappush(self.low, -heapq.heappop(self.high)) def median(self): if len(self.low) > len(self.high): return -self.low[0] return (-self.low[0] + self.high[0]) / 2 The push-then-move trick guarantees the ordering invariant without extra comparisons, and the final check restores the size invariant. Each add is O(log n) and median is O(1). Related problems that use two heaps 1. Sliding Window Median: same structure, but you must also remove elements leaving the window. Use lazy deletion with a hash map of "to delete" counts, and clean the heap tops when they are stale. 2. IPO / Maximize Capital: one min-heap of projects by required capital and one max-heap of affordable projects by profit. Move projects across as your capital grows. 3. Scheduling problems: a min-heap of available servers and another of busy servers ordered by finish time. 4. Balancing two groups: any time you need the boundary between "smaller half" and "larger half", two heaps are a candidate. Follow-up questions interviewers ask - What if all numbers are integers in [0, 100]? Then a counting array of 101 buckets gives O(1) inserts and O(100) median, which is effectively constant. - What if 99% of numbers fall in [0, 100]? Use buckets for that range plus counters or small heaps for the outliers. - How would this work in a distributed system? Discuss approximate quantile sketches like t-digest as a trade-off between accuracy and memory. Common mistakes - Forgetting that Python's heapq is a min-heap only and mixing up negated values. - Letting the size difference grow beyond one. - Returning an integer when the even-count median should be a float. How to explain it clearly Lead with the invariant: "Everything in the left heap is at most everything in the right heap, and their sizes differ by at most one." Interviewers want to hear that sentence before they see code, because it shows you know why the solution is correct. Holding a clear invariant in your head while talking and typing is hard under pressure. Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep your explanation structured as you code. It works best on top of genuine practice. Takeaway: when you need a running boundary between halves of a dataset, think two heaps.