Two Heaps Interview Pattern: When to Use It and 5 Practice Problems (2026)

When a coding interview asks you to maintain a dynamic order statistic—think median of a growing list, sliding‑window median, or the k‑th largest element—most candidates reach for a balanced binary search tree or a sorted list. Those structures work but carry extra overhead and more complex code. The two‑heaps pattern solves the same class of problems with just two priority queues: a max‑heap for the lower half of the data and a min‑heap for the upper half. By keeping the two halves balanced, you can answer the required query in constant time while each insertion or deletion stays logarithmic.

Why Two Heaps Work

A max‑heap gives you the largest element of its set in O(1) time, and a min‑heap gives you the smallest element of its set in O(1). If you split the numbers into two groups—those less than or equal to the median and those greater than the median—then the median is either the top of the max‑heap (when the total count is odd) or the average of the two tops (when even). Maintaining the size invariant (the two heaps differ by at most one element) guarantees that the median is always at the top of one of the heaps.

Signals That Call for Two Heaps

If you see any of these phrases, pause and consider the two‑heaps approach before pulling out a tree or a sort.

Worked Example: Running Median

Problem: Given a list of integers arriving one by one, output the median after each insertion.

Approach:

1. Initialise an empty max‑heap low (store negatives to simulate a max‑heap) and an empty min‑heap high.
2. For each new number x:
   • If low is empty or x ≤ -low[0], push -x onto low; otherwise push x onto high.
   • Re‑balance: if len(low) > len(high) + 1, move the top of low to high; if len(high) > len(low), move the top of high to low.
3. The median is -low[0] when len(low) > len(high), otherwise ( -low[0] + high[0] ) / 2.

Python code:

import heapq

def running_median(stream):
    low = []   # max‑heap (store negatives)
    high = []  # min‑heap
    medians = []
    for x in stream:
        if not low or x <= -low[0]:
            heapq.heappush(low, -x)
        else:
            heapq.heappush(high, x)
        # rebalance
        if len(low) > len(high) + 1:
            heapq.heappush(high, -heapq.heappop(low))
        elif len(high) > len(low):
            heapq.heappush(low, -heapq.heappop(high))
        # compute median
        if len(low) > len(high):
            medians.append(-low[0])
        else:
            medians.append((-low[0] + high[0]) / 2)
    return medians


print(running_median([5, 15, 1, 3, 8, 7, 9, 10, 6, 11, 4]))

The function runs in O(n log n) time and O(n) space, with each insertion costing only a couple of heap operations.

Complexity at a Glance

• Insertion / Deletion: O(log n) – each heap push/pop is logarithmic.
• Query (median, k‑th, etc.): O(1) – just look at the heap top(s).
• Space: O(n) – you store every element in one of the two heaps.

Common Pitfalls and How to Avoid Them

1. Off‑by‑one size errors – The invariant is that len(low) >= len(high) and the difference is at most one. After every insertion, explicitly rebalance; a missing rebalance step will break the median logic.
2. Wrong heap direction – Python’s heapq is a min‑heap. Remember to store negatives for the max‑heap side, or use a wrapper class if you prefer readability.
3. Lazy deletions in sliding windows – When elements leave the window, you can’t remove them directly from a heap efficiently. Mark them in a hashmap and discard them when they reach the top.
4. Floating‑point vs integer median – If the problem expects an integer median (e.g., floor division), cast appropriately; otherwise return a float for the average of two middles.

Five Practice Problems

Below are five problems that each highlight a different twist on the two‑heaps pattern. The descriptions avoid copying any copyrighted wording.

1. Sliding Window Median – Given an array and a window size k, output the median of each contiguous subarray of length k. Hint: Use two heaps plus a hashmap to lazily delete elements that fall out of the window.
2. Kth Largest Element in a Stream – Implement a class with add(num) and top() that returns the k‑th largest element seen so far. Hint: Keep a min‑heap of size k; everything larger stays outside.
3. Find Median of Two Sorted Arrays (Logarithmic) – Merge two sorted lists implicitly to find the median without full concatenation. Hint: Treat the problem as a partition and use two heaps to simulate the left/right halves.
4. Dynamic Range Median Queries – Support inserting numbers and answering median queries on any prefix [0, i]. Hint: Maintain two heaps while processing the array left‑to‑right; each prefix query is O(1).
5. Maximum Frequency Stack – Design a stack that pops the most frequent element, breaking ties by most recent. Hint: Use a hash map of frequencies and a heap keyed by (-freq, -timestamp) to retrieve the correct element quickly.

Working through these will cement the pattern and expose you to variations like lazy deletion, fixed‑size heaps, and custom comparator logic.

How to Practice This

1. Implement the core pattern – Write a small script that reads numbers from stdin and prints the running median. Run it against random data and compare against a naïve sorted list implementation.
2. Solve one of the practice problems – Pick a problem, code it from scratch, and then refactor to extract a reusable TwoHeaps helper class.
3. Explain it aloud – Use Call Assistant to rehearse a concise explanation (45‑90 seconds). The tool can keep your story grounded in your own experience and help you stay on track during the interview.

---

FAQ

• Q: When should I prefer a balanced BST over two heaps? A: Use a BST if you need ordered iteration, range queries, or deletions that aren’t tied to the median. Two heaps excel when you only need the median or a single order statistic.

• Q: Can I use the two‑heaps pattern for finding the mode? A: Not directly. Mode requires counting frequencies, so a hashmap or tree map is more appropriate.

• Q: How do I handle duplicate values in the heaps? A: Duplicates are fine; heap operations treat equal keys uniformly. Just ensure your rebalance logic accounts for total element count, not unique values.

• Q: Is there a memory‑optimal variant? A: For very large streams you can keep only the necessary portion (e.g., a min‑heap of size k for k‑th largest). The two‑heap core still uses O(n) space if you store everything, but you can trim one side when you only need a fixed‑size statistic.