Loading…

hardHeapLC #295Frequently asked

Find Median from Data Stream

Q: How do you solve Find Median from Data Stream using the Sorted Insertion (Baseline) approach?

When to use it: Mention briefly to anchor the cost, then pivot — it's too slow per insert for a real stream. Keep an array sorted as numbers arrive. To add, binary-search for the insertion index and splice the value in. The median is then trivially the middle index (odd count) or the average of the two middle indices (even count). **Why it's tempting.** findMedian becomes a single index calculation — O(1). For a few inserts followed by many median queries, it's even reasonable. **Why it fails at scale.** The insertion itself shifts elements: adding to the front of a 50,000-element array moves all of them. Across n adds that's O(n²) overall — too slow for the call volume. We need an insert that's logarithmic, which points to heaps. Time complexity: O(n) per add, O(1) median. Space complexity: O(n).

Q: How do you solve Find Median from Data Stream using the Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal) approach?

When to use it: The expected answer. Phrase it as 'split the data into a lower half and an upper half, each kept heap-ordered toward the boundary'. Picture the sorted stream cut in two. The **lower half** lives in a max-heap `low` (top = the *largest* of the small numbers). The **upper half** lives in a min-heap `high` (top = the *smallest* of the big numbers). The median is precisely at this seam — that's the entire idea. **Two invariants do all the work.** - *Order*: every value in `low` ≤ every value in `high`. This guarantees the two tops straddle the true middle. - *Balance*: the heaps' sizes differ by at most one, and we let `low` be the one allowed to hold the extra element on odd counts. **The insert dance — push, transfer, rebalance.** Always push the new number onto `low` first. Then pop `low`'s top and push it onto `high`. That transfer guarantees the *order* invariant: whatever the largest of the lower half was, it now sits in the upper half if it belongs there. But the transfer may leave `high` bigger than `low`, breaking *balance* — so if `high` is larger, move its top back to `low`. After this fixed sequence both invariants hold again. **Reading the median.** If `low` has one more element than `high` (odd total), the median is `low`'s top. If the sizes are equal (even total), the median is the average of the two tops. Both are O(1). **Python max-heap trick.** `heapq` only offers a min-heap. To make `low` behave as a max-heap, push **negated** values; the smallest negative corresponds to the largest original value. Negate again when you read it back. Forgetting a negation is the #1 bug here. Time complexity: O(log n) addNum, O(1) findMedian. Space complexity: O(n).

LCPractice

Heap & Priority Queue · 2 of 9 · 11 min

The median is the middle value in an ordered list. If the list has an even number of elements, the median is the mean of the two middle values.

Implement the MedianFinder class:

MedianFinder() initialises the object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10⁻⁵ of the actual answer are accepted.

In plain English

Design an object that ingests numbers one at a time and can report the current median on demand. The challenge is that the stream never stops, so we can't sort once — every insert must keep the structure 'median-ready' cheaply.

Examples

Example 1

Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, then 2.0
Note: After 1,2 the two middles are 1 and 2 → mean 1.5. After adding 3, the ordered set is [1,2,3] → middle is 2.

Example 2

Input: addNum(5), findMedian()
Output: 5.0
Note: Single element; it is its own median.

Example 3

Input: addNum(-1), addNum(-2), addNum(-3), findMedian()
Output: -2.0
Note: Ordered: [-3,-2,-1]; the middle of three is -2. Negatives behave identically.

Constraints

-10⁵ ≤ num ≤ 10⁵
There will be at least one element before findMedian is called
At most 5 × 10⁴ calls to addNum and findMedian
Follow-up: if all numbers are in [0, 100], can you optimise? What if 99% are in [0, 100]?

Clarifying questions4First question: Can findMedian be called before any number is added?Explore questions

Q1.Can findMedian be called before any number is added?
The constraints guarantee at least one addNum first, so I won't handle the empty case — though I'd guard it in production.
Q2.How many calls, and what's the read/write mix?
Up to 5×10⁴ mixed calls. Because findMedian can be called as often as addNum, I want findMedian to be O(1) and addNum O(log n).
Q3.Are the values bounded?
In general [-10⁵, 10⁵]. The follow-up restricts to [0, 100], which unlocks an O(1)-update counting-array solution.
Q4.Do duplicates occur?
Yes, duplicates are fine — heaps handle them naturally and the median definition is unaffected.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Maintain two heaps that split the numbers in half: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced (differ by at most one). The median is the top of the larger heap, or the average of both tops when sizes are equal. addNum is O(log n); findMedian is O(1).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design a data structure (not just an algorithm) that supports two operations efficiently, and whether you can state and preserve invariants across mutations.

Where candidates slip

Re-sorting or re-scanning the whole collection on each findMedian (O(n log n) or O(n) per query), or letting the two heaps drift out of balance so the median read is wrong.

How to stand out

State the two invariants (order and balance) explicitly, show the push-transfer-rebalance sequence preserves both, and discuss follow-ups: bounded range → counting buckets, and the 99% in [0,100] variant.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sorted Insertion (Baseline)	`O(n) per add, O(1) median`	`O(n)`	Mention briefly to anchor the cost, then pivot — it's too slow per insert for a real stream.	Read
2	Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal)Optimal	`O(log n) addNum, O(1) findMedian`	`O(n)`	The expected answer. Phrase it as 'split the data into a lower half and an upper half, each kept heap-ordered toward the boundary'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMedian of a growing streamStatic data or a stream?StaticStreamExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sorted Insertion (Baseline)

TimeO(n) per add, O(1) medianSpaceO(n)

Mention briefly to anchor the cost, then pivot — it's too slow per insert for a real stream.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you kept the numbers sorted at all times, where would the median always be?

2Hint 2Explore hint

Insert each new number into its correct position in a sorted list (binary search to find the spot).

3Hint 3Explore hint

Finding the spot is O(log n), but shifting elements to insert is O(n) — that's the bottleneck for a long stream.

A · Core idea

Keep an array sorted as numbers arrive. To add, binary-search for the insertion index and splice the value in. The median is then trivially the middle index (odd count) or the average of the two middle indices (even count).

Why it's tempting. findMedian becomes a single index calculation — O(1). For a few inserts followed by many median queries, it's even reasonable.

Why it fails at scale. The insertion itself shifts elements: adding to the front of a 50,000-element array moves all of them. Across n adds that's O(n²) overall — too slow for the call volume. We need an insert that's logarithmic, which points to heaps.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

add 2, add 1, add 3, findMedian

add 2

insert → [2]

Statemedian 2

Final result2.0

C · Code with teaching comments

Reference implementation previewclass MedianFinder { private List<Integer> data = new ArrayList<>(); public void addNum(int num) { int lo = 0, hi = data.size();Explore the full code

solution.javaJava

Sorted Insertion (Baseline) — reference

3 teaching notes

1
class MedianFinder {
2
    private List<Integer> data = new ArrayList<>();
3
 
4
    public void addNum(int num) {
5
        int lo = 0, hi = data.size();
6
        while (lo < hi) {
7
            // Unsigned shift avoids overflow on (lo+hi) for large indices.
8
            int mid = (lo + hi) >>> 1;
9
            if (data.get(mid) < num) lo = mid + 1;
10
            else hi = mid;
11
        }
12
        // The insertion shifts every later element — the O(n) cost that sinks this
13
        // approach.
14
        data.add(lo, num); // O(n) shift
15
    }
16
 
17
    public double findMedian() {
18
        int n = data.size();
19
        if (n % 2 == 1) return data.get(n / 2);
20
        return (data.get(n / 2 - 1) + data.get(n / 2)) / 2.0;
21
    }
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) per add, O(1) median timeO(n) spaceOpen the invariant and proofExplore the proof

Keeping data fully sorted is overkill: the median only needs the boundary between the lower and upper halves, not a total order. Tracking just that boundary is what makes the two-heap solution fast.

ComplexityO(n) per add, O(1) median time, O(n) space — Binary search locates the insertion point in O(log n), but array insertion shifts up to n elements → O(n) per add. The median is then a direct index lookup, O(1).

E · Edge cases and pitfalls2Assuming list insertion is cheap — it shifts O(n) elements.Explore edge cases

Pitfalls

Assuming list insertion is cheap — it shifts O(n) elements.
Integer division when averaging the two middles — divide by 2.0, not 2.

03.2

Approach 2 of 2 · Optimal

Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal)

TimeO(log n) addNum, O(1) findMedianSpaceO(n)

The expected answer. Phrase it as 'split the data into a lower half and an upper half, each kept heap-ordered toward the boundary'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The median only depends on the boundary between the smaller half and the larger half. What if you stored those two halves separately?

2Hint 2Explore hint

Keep a max-heap of the lower half (so its top is the largest small value) and a min-heap of the upper half (so its top is the smallest large value). The median lives at those two tops.

3Hint 3Explore hint

On each insert, push, then move the boundary element across so every low ≤ every high, then rebalance sizes so they differ by at most one. Median = the larger heap's top, or the average of both tops.

A · Core idea

Picture the sorted stream cut in two. The lower half lives in a max-heap low (top = the largest of the small numbers). The upper half lives in a min-heap high (top = the smallest of the big numbers). The median is precisely at this seam — that's the entire idea.

Two invariants do all the work.

Order: every value in low ≤ every value in high. This guarantees the two tops straddle the true middle.
Balance: the heaps' sizes differ by at most one, and we let low be the one allowed to hold the extra element on odd counts.

The insert dance — push, transfer, rebalance. Always push the new number onto low first. Then pop low's top and push it onto high. That transfer guarantees the order invariant: whatever the largest of the lower half was, it now sits in the upper half if it belongs there. But the transfer may leave high bigger than low, breaking balance — so if high is larger, move its top back to low. After this fixed sequence both invariants hold again.

Reading the median. If low has one more element than high (odd total), the median is low's top. If the sizes are equal (even total), the median is the average of the two tops. Both are O(1).

Python max-heap trick. heapq only offers a min-heap. To make low behave as a max-heap, push negated values; the smallest negative corresponds to the largest original value. Negate again when you read it back. Forgetting a negation is the #1 bug here.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

add 1, add 2, findMedian, add 3, findMedian

Array state

after add 1

low=[1] high=[]

median ↓

low:1

[0]

high:-

[1]

Current pointerResolved stateNot processed

Final result1.5 then 2.0

C · Code with teaching comments

solution.javaJava

Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal) — optimal

5 teaching notes

1
class MedianFinder {
2
    // low: max-heap of the smaller half. high: min-heap of the larger half.
3
    private PriorityQueue<Integer> low =
4
        // reverseOrder turns Java's default min-heap into a MAX-heap for the lower
5
        // half.
6
        new PriorityQueue<>(Collections.reverseOrder());
7
    private PriorityQueue<Integer> high = new PriorityQueue<>();
8
 
9
    public void addNum(int num) {
10
        low.offer(num);            // 1) always add to low
11
        high.offer(low.poll());    // 2) move low's max into high (order invariant)
12
        if (high.size() > low.size()) {
13
            low.offer(high.poll()); // 3) rebalance so low ≥ high in size
14
        }
15
    }
16
 
17
    public double findMedian() {
18
        if (low.size() > high.size()) {
19
            return low.peek();
20
        }
21
        // Equal sizes (even total) → median is the average of the two boundary tops.
22
        return (low.peek() + high.peek()) / 2.0;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(log n) addNum, O(1) findMedian timeO(n) spaceOpen the invariant and proofExplore the proof

The transfer-then-rebalance pattern is a tiny, branch-free way to maintain a sorted partition under insertion. By always routing the newcomer through low and shipping the boundary across, you never have to compare the new value against the heap tops yourself — the heaps' own ordering decides where it lands.

ComplexityO(log n) addNum, O(1) findMedian time, O(n) space — Each addNum does a constant number of heap pushes/pops, each O(log n). findMedian just reads one or two heap tops — O(1). Both heaps together hold all n elements → O(n) space.

E · Edge cases and pitfalls6single addNum(5) — Push 5→low, move to high, high bigger → move back; low=[5], high=[]. findMedian returns 5.0.Explore edge cases

Edge cases handled

single addNum(5)Push 5→low, move to high, high bigger → move back; low=[5], high=[]. findMedian returns 5.0.
duplicates: add 2, add 2low=[2], high=[2]; median (2+2)/2 = 2.0. Duplicates split across the seam fine.
strictly decreasing inputEach smaller value enters low and the transfer keeps order; balance logic still yields the correct middle.

Pitfalls

Forgetting to negate when reading low's top in Python — returns the wrong sign/value.
Comparing the new number to the heap tops manually instead of using push-transfer-rebalance — error-prone branching.
Letting balance drift (rebalancing on the wrong side) so the larger heap isn't consistently `low` — median read picks the wrong top.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass MedianFinder { // low: max-heap of the smaller half. high: min-heap of the larger half. private PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); private PriorityQueue<Integer> high = new PriorityQueue<>();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the max-heap negation in Python

heapq is a min-heap. Without negating, `low` keeps its smallest on top, so `low[0]` is not the largest of the lower half and the median read is wrong.

Explore the code comparison

Don't write this

heapq.heappush(self.low, num)        # min-heap, wrong end on top
heapq.heappush(self.high, heapq.heappop(self.low))
# findMedian reads self.low[0] expecting the MAX — it's the min

Write this instead

heapq.heappush(self.low, -num)       # negate → behaves as max-heap
heapq.heappush(self.high, -heapq.heappop(self.low))
# read -self.low[0] to recover the true max

Rebalancing on the wrong side

If you let `high` be the heap that may hold the extra element but read the median from `low`, odd counts return the wrong value. Pick one heap (here `low`) to own the surplus and be consistent.

Explore the code comparison

Don't write this

// surplus goes to high, but findMedian reads low
if (low.size() > high.size()) high.offer(low.poll());
// ...
if (low.size() != high.size()) return low.peek();

Write this instead

// surplus always goes to low; read low when sizes differ
low.offer(num);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
// findMedian: if (low.size() > high.size()) return low.peek();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two balanced heaps (max-heap low half, min-heap high half)

Code pattern to memorize

addNum(x):
    push x onto low (max-heap)
    move low.top -> high      # ensure every low ≤ every high
    if len(high) > len(low):  # rebalance sizes
        move high.top -> low
findMedian():
    if len(low) > len(high): return low.top
    return (low.top + high.top) / 2

Rules to remember

1low is a max-heap (its top is the largest of the small half); high is a min-heap (its top is the smallest of the big half).
2Invariant 1 — order: every element in low ≤ every element in high.
3Invariant 2 — balance: 0 ≤ len(low) − len(high) ≤ 1. Keep low the one that may be larger by one.
4Python has only a min-heap — simulate a max-heap by negating values pushed to low.
5The 'push then transfer then rebalance' dance enforces BOTH invariants on every insert without sorting.

Use this pattern when

Running median / running percentile over a stream of numbers
You need the middle element repeatedly as data arrives
Any 'maintain two halves and query the boundary' design problem
Online algorithm where re-sorting on every query is too slow

Choose another pattern when

Data is static and given upfront → just sort once, O(n log n)
Values are bounded small integers → a counting/Fenwick approach can give O(1) updates
You only need the median once → nth_element / quickselect is O(n)

Interview takeaway

Two heaps facing each other turn 'find the middle of a growing set' into O(log n) inserts and O(1) median reads. Whenever a problem needs the boundary between the smaller and larger halves of streaming data, reach for a max-heap/min-heap pair.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo balanced heaps maintaining a median boundary. The signature design pattern for running median/percentile over a stream. For bounded values switch to a counting array; for windows add removal support (Sliding Window Median).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sliding Window Median
Coming soon
Same two heaps, but support removal as the window slides — use lazy deletion or a TreeMap/multiset.
Kth Largest Element in an Array
Coming soon
Single size-k heap — a simpler cousin of the boundary-heap idea.
Kth Largest Element in a Stream
Coming soon
Maintain a min-heap of size k for the streaming Kth largest — design-problem sibling.
Median of Two Sorted Arrays
Coming soon
Static median via binary search on the partition — the offline counterpart.

Same pattern

←

Top K Frequent Elements

Continue · Next problem

K Closest Points to Origin

hardHeapLC #295Frequently asked

Find Median from Data Stream

LCPractice

Heap & Priority Queue · 2 of 9 · 11 min

The median is the middle value in an ordered list. If the list has an even number of elements, the median is the mean of the two middle values.

Implement the MedianFinder class:

MedianFinder() initialises the object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10⁻⁵ of the actual answer are accepted.

In plain English

Examples

Example 1

Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, then 2.0
Note: After 1,2 the two middles are 1 and 2 → mean 1.5. After adding 3, the ordered set is [1,2,3] → middle is 2.

Example 2

Input: addNum(5), findMedian()
Output: 5.0
Note: Single element; it is its own median.

Example 3

Input: addNum(-1), addNum(-2), addNum(-3), findMedian()
Output: -2.0
Note: Ordered: [-3,-2,-1]; the middle of three is -2. Negatives behave identically.

Constraints

-10⁵ ≤ num ≤ 10⁵
There will be at least one element before findMedian is called
At most 5 × 10⁴ calls to addNum and findMedian
Follow-up: if all numbers are in [0, 100], can you optimise? What if 99% are in [0, 100]?

Clarifying questions4First question: Can findMedian be called before any number is added?Explore questions

Q1.Can findMedian be called before any number is added?
The constraints guarantee at least one addNum first, so I won't handle the empty case — though I'd guard it in production.
Q2.How many calls, and what's the read/write mix?
Up to 5×10⁴ mixed calls. Because findMedian can be called as often as addNum, I want findMedian to be O(1) and addNum O(log n).
Q3.Are the values bounded?
In general [-10⁵, 10⁵]. The follow-up restricts to [0, 100], which unlocks an O(1)-update counting-array solution.
Q4.Do duplicates occur?
Yes, duplicates are fine — heaps handle them naturally and the median definition is unaffected.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design a data structure (not just an algorithm) that supports two operations efficiently, and whether you can state and preserve invariants across mutations.

Where candidates slip

Re-sorting or re-scanning the whole collection on each findMedian (O(n log n) or O(n) per query), or letting the two heaps drift out of balance so the median read is wrong.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sorted Insertion (Baseline)	`O(n) per add, O(1) median`	`O(n)`	Mention briefly to anchor the cost, then pivot — it's too slow per insert for a real stream.	Read
2	Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal)Optimal	`O(log n) addNum, O(1) findMedian`	`O(n)`	The expected answer. Phrase it as 'split the data into a lower half and an upper half, each kept heap-ordered toward the boundary'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sorted Insertion (Baseline)

TimeO(n) per add, O(1) medianSpaceO(n)

Mention briefly to anchor the cost, then pivot — it's too slow per insert for a real stream.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you kept the numbers sorted at all times, where would the median always be?

2Hint 2Explore hint

Insert each new number into its correct position in a sorted list (binary search to find the spot).

3Hint 3Explore hint

Finding the spot is O(log n), but shifting elements to insert is O(n) — that's the bottleneck for a long stream.

A · Core idea

Why it's tempting. findMedian becomes a single index calculation — O(1). For a few inserts followed by many median queries, it's even reasonable.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

add 2, add 1, add 3, findMedian

add 2

insert → [2]

Statemedian 2

Final result2.0

C · Code with teaching comments

Reference implementation previewclass MedianFinder { private List<Integer> data = new ArrayList<>(); public void addNum(int num) { int lo = 0, hi = data.size();Explore the full code

solution.javaJava

Sorted Insertion (Baseline) — reference

3 teaching notes

1
class MedianFinder {
2
    private List<Integer> data = new ArrayList<>();
3
 
4
    public void addNum(int num) {
5
        int lo = 0, hi = data.size();
6
        while (lo < hi) {
7
            // Unsigned shift avoids overflow on (lo+hi) for large indices.
8
            int mid = (lo + hi) >>> 1;
9
            if (data.get(mid) < num) lo = mid + 1;
10
            else hi = mid;
11
        }
12
        // The insertion shifts every later element — the O(n) cost that sinks this
13
        // approach.
14
        data.add(lo, num); // O(n) shift
15
    }
16
 
17
    public double findMedian() {
18
        int n = data.size();
19
        if (n % 2 == 1) return data.get(n / 2);
20
        return (data.get(n / 2 - 1) + data.get(n / 2)) / 2.0;
21
    }
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) per add, O(1) median timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls2Assuming list insertion is cheap — it shifts O(n) elements.Explore edge cases

Pitfalls

Assuming list insertion is cheap — it shifts O(n) elements.
Integer division when averaging the two middles — divide by 2.0, not 2.

03.2

Approach 2 of 2 · Optimal

Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal)

TimeO(log n) addNum, O(1) findMedianSpaceO(n)

The expected answer. Phrase it as 'split the data into a lower half and an upper half, each kept heap-ordered toward the boundary'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The median only depends on the boundary between the smaller half and the larger half. What if you stored those two halves separately?

2Hint 2Explore hint

Keep a max-heap of the lower half (so its top is the largest small value) and a min-heap of the upper half (so its top is the smallest large value). The median lives at those two tops.

3Hint 3Explore hint

A · Core idea

Two invariants do all the work.

Order: every value in low ≤ every value in high. This guarantees the two tops straddle the true middle.
Balance: the heaps' sizes differ by at most one, and we let low be the one allowed to hold the extra element on odd counts.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

add 1, add 2, findMedian, add 3, findMedian

Array state

after add 1

low=[1] high=[]

median ↓

low:1

[0]

high:-

[1]

Current pointerResolved stateNot processed

Final result1.5 then 2.0

C · Code with teaching comments

solution.javaJava

Two Heaps — Max-Heap Low Half, Min-Heap High Half (Optimal) — optimal

5 teaching notes

1
class MedianFinder {
2
    // low: max-heap of the smaller half. high: min-heap of the larger half.
3
    private PriorityQueue<Integer> low =
4
        // reverseOrder turns Java's default min-heap into a MAX-heap for the lower
5
        // half.
6
        new PriorityQueue<>(Collections.reverseOrder());
7
    private PriorityQueue<Integer> high = new PriorityQueue<>();
8
 
9
    public void addNum(int num) {
10
        low.offer(num);            // 1) always add to low
11
        high.offer(low.poll());    // 2) move low's max into high (order invariant)
12
        if (high.size() > low.size()) {
13
            low.offer(high.poll()); // 3) rebalance so low ≥ high in size
14
        }
15
    }
16
 
17
    public double findMedian() {
18
        if (low.size() > high.size()) {
19
            return low.peek();
20
        }
21
        // Equal sizes (even total) → median is the average of the two boundary tops.
22
        return (low.peek() + high.peek()) / 2.0;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(log n) addNum, O(1) findMedian timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6single addNum(5) — Push 5→low, move to high, high bigger → move back; low=[5], high=[]. findMedian returns 5.0.Explore edge cases

Edge cases handled

single addNum(5)Push 5→low, move to high, high bigger → move back; low=[5], high=[]. findMedian returns 5.0.
duplicates: add 2, add 2low=[2], high=[2]; median (2+2)/2 = 2.0. Duplicates split across the seam fine.
strictly decreasing inputEach smaller value enters low and the transfer keeps order; balance logic still yields the correct middle.

Pitfalls

Forgetting to negate when reading low's top in Python — returns the wrong sign/value.
Comparing the new number to the heap tops manually instead of using push-transfer-rebalance — error-prone branching.
Letting balance drift (rebalancing on the wrong side) so the larger heap isn't consistently `low` — median read picks the wrong top.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the max-heap negation in Python

heapq is a min-heap. Without negating, `low` keeps its smallest on top, so `low[0]` is not the largest of the lower half and the median read is wrong.

Explore the code comparison

Don't write this

heapq.heappush(self.low, num)        # min-heap, wrong end on top
heapq.heappush(self.high, heapq.heappop(self.low))
# findMedian reads self.low[0] expecting the MAX — it's the min

Write this instead

heapq.heappush(self.low, -num)       # negate → behaves as max-heap
heapq.heappush(self.high, -heapq.heappop(self.low))
# read -self.low[0] to recover the true max

Rebalancing on the wrong side

If you let `high` be the heap that may hold the extra element but read the median from `low`, odd counts return the wrong value. Pick one heap (here `low`) to own the surplus and be consistent.

Explore the code comparison

Don't write this

// surplus goes to high, but findMedian reads low
if (low.size() > high.size()) high.offer(low.poll());
// ...
if (low.size() != high.size()) return low.peek();

Write this instead

// surplus always goes to low; read low when sizes differ
low.offer(num);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
// findMedian: if (low.size() > high.size()) return low.peek();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two balanced heaps (max-heap low half, min-heap high half)

Code pattern to memorize

addNum(x):
    push x onto low (max-heap)
    move low.top -> high      # ensure every low ≤ every high
    if len(high) > len(low):  # rebalance sizes
        move high.top -> low
findMedian():
    if len(low) > len(high): return low.top
    return (low.top + high.top) / 2

Rules to remember

1low is a max-heap (its top is the largest of the small half); high is a min-heap (its top is the smallest of the big half).
2Invariant 1 — order: every element in low ≤ every element in high.
3Invariant 2 — balance: 0 ≤ len(low) − len(high) ≤ 1. Keep low the one that may be larger by one.
4Python has only a min-heap — simulate a max-heap by negating values pushed to low.
5The 'push then transfer then rebalance' dance enforces BOTH invariants on every insert without sorting.

Use this pattern when

Running median / running percentile over a stream of numbers
You need the middle element repeatedly as data arrives
Any 'maintain two halves and query the boundary' design problem
Online algorithm where re-sorting on every query is too slow

Choose another pattern when

Data is static and given upfront → just sort once, O(n log n)
Values are bounded small integers → a counting/Fenwick approach can give O(1) updates
You only need the median once → nth_element / quickselect is O(n)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sliding Window Median
Coming soon
Same two heaps, but support removal as the window slides — use lazy deletion or a TreeMap/multiset.
Kth Largest Element in an Array
Coming soon
Single size-k heap — a simpler cousin of the boundary-heap idea.
Kth Largest Element in a Stream
Coming soon
Maintain a min-heap of size k for the streaming Kth largest — design-problem sibling.
Median of Two Sorted Arrays
Coming soon
Static median via binary search on the partition — the offline counterpart.

Same pattern

←

Top K Frequent Elements

Continue · Next problem

K Closest Points to Origin