Loading…

hardHeapFrequently asked

Find the Running Median

Q: How do you solve Find the Running Median using the Brute Force — Insert into a Sorted List approach?

When to use it: State first to frame the cost; it's the obvious incremental idea before heaps. Keep a list of all values seen so far in sorted order. For each new value, binary-search its insertion index and insert it there, then read the median from the middle position(s). **Why it's the natural first idea.** It directly mirrors the definition — 'the median is the middle of the sorted values' — and gives O(1) median reads once the list is maintained. **Why it's too slow.** Although finding the position is O(log n), physically inserting into a contiguous list shifts every element after it, costing O(n) per step and O(n²) overall. For n = 10⁵ that's ~10¹⁰ shifts — too slow. A balanced BST or skip list would make insertion O(log n), but that's more machinery than the two-heap trick, which needs no ordering of the whole sequence — only the boundary. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Find the Running Median using the Two Heaps — Max-Heap + Min-Heap (Optimal) approach?

When to use it: The expected answer — describe it as 'split the stream at the median with a max-heap and a min-heap'. Split the numbers into a smaller half (`lower`, a **max-heap**) and a larger half (`upper`, a **min-heap**). The largest of the small half (`lower.top`) and the smallest of the large half (`upper.top`) straddle the median. **Routing a new value.** If `lower` is empty or `x <= lower.top`, `x` belongs in the small half → push to `lower`; otherwise push to `upper`. This keeps every element in `lower` ≤ every element in `upper`. **Rebalancing.** After the push, one heap may be two elements ahead. Restore the invariant `len(lower) == len(upper)` or `len(lower) == len(upper) + 1`: if `lower` is more than one ahead, pop its max and push onto `upper`; if `upper` is ahead at all, pop its min and push onto `lower`. We deliberately let `lower` carry the extra element on odd counts so the odd-median is simply `lower.top`. **Reading the median.** If the counts are equal, the two middle elements are exactly the two tops, so the median is `(lower.top + upper.top) / 2.0`. If `lower` has one more, the single middle element is `lower.top`. Both are O(1). **Why two heaps beat a sorted list.** A heap gives O(1) access to just the boundary element we need and O(log n) insertion, instead of paying O(n) to keep the whole sequence ordered. We never need the full order — only the median boundary. **Language notes.** Java's `PriorityQueue` is a min-heap; build the max-heap with `new PriorityQueue<>(Collections.reverseOrder())`. Python's `heapq` is min-only, so implement the max-heap by pushing negated values and negating on peek. Time complexity: O(n log n). Space complexity: O(n).

Heap & Priority Queue · 9 of 9 · 11 min

Numbers arrive one at a time. After reading each number, print the median of all numbers seen so far.

If the count of numbers seen is odd, the median is the middle element of the sorted sequence. If it is even, the median is the average of the two middle elements.

Print each median on its own line, formatted to one decimal place.

In plain English

We need the median after every insertion, not just at the end, and elements keep coming. Re-sorting each time is O(n log n) per step. The efficient idea is to keep the sequence split into a smaller half and a larger half so the median is always at the boundary — and a heap gives O(1) access to the boundary element of each half.

Examples

Example 1

Input: stream = [12, 4, 5, 3, 8, 7]
Output: 12.0 8.0 5.0 4.5 5.0 6.0
Note: After 12 → 12.0. After 12,4 → (4+12)/2 = 8.0. After +5 → middle of [4,5,12] = 5.0. After +3 → ([3,4,5,12]) (4+5)/2 = 4.5. After +8 → middle of [3,4,5,8,12] = 5.0. After +7 → ([3,4,5,7,8,12]) (5+7)/2 = 6.0.

Example 2

Input: stream = [1, 2, 3, 4, 5]
Output: 1.0 1.5 2.0 2.5 3.0
Note: Sorted prefixes [1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5] give medians 1.0, 1.5, 2.0, 2.5, 3.0.

Constraints

1 ≤ n ≤ 10⁵ (numbers in the stream)
0 ≤ arr[i] ≤ 10⁵
Print each running median to exactly one decimal place
Median of an even count is the average of the two middle values (may end in .5)

Clarifying questions4First question: Do I report the median after every insertion or only once?Explore questions

Q1.Do I report the median after every insertion or only once?
After every insertion — that's why an incremental structure (two heaps) beats re-sorting.
Q2.How is the even-count median defined?
The average of the two middle elements, so it can be a .5 value — use floating-point division.
Q3.What output format is expected?
Each median on its own line, formatted to one decimal place (e.g. 8.0, 4.5).
Q4.Can numbers repeat or be zero?
Yes. Duplicates and zeros are ordinary values; the comparison with the max-heap top still routes them correctly.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Maintain two heaps: a MAX-heap `lower` holding the smaller half and a MIN-heap `upper` holding the larger half. Each new value goes to a half, then you rebalance so their sizes differ by at most one. The median is the top of `lower` when it has the extra element, or the average of both tops when sizes are equal. Each insertion is O(log n); printing after each gives O(n log n) total and O(1) median lookup.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for two heaps to get O(log n) insertion with O(1) median, and whether you get the rebalancing invariant and even/odd median formula exactly right.

Where candidates slip

Letting the heap sizes drift apart, reading the wrong heap's top, integer-dividing the even-case median (losing the .5), or mixing up which heap is max vs min.

How to stand out

State the size invariant precisely, explain why the two tops bracket the median, and mention the language-specific max-heap trick (reverseOrder in Java, negation in Python).

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	Brute Force — Insert into a Sorted List	`O(n²)`	`O(n)`	State first to frame the cost; it's the obvious incremental idea before heaps.	Read
2	Two Heaps — Max-Heap + Min-Heap (Optimal)Optimal	`O(n log n)`	`O(n)`	The expected answer — describe it as 'split the stream at the median with a max-heap and a min-heap'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewNew value xx <= lower.top (or lower empty)?YesNoExplore 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

Brute Force — Insert into a Sorted List

TimeO(n²)SpaceO(n)

State first to frame the cost; it's the obvious incremental idea before heaps.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you kept the numbers seen so far in sorted order, where is the median?

2Hint 2Explore hint

Maintain a sorted list. Insert each new value in its correct position (binary search to find it, but the shift is the costly part).

3Hint 3Explore hint

Median is then the middle element (or average of the two middle) — O(1) to read, but each insertion shifts elements in O(n).

A · Core idea

Keep a list of all values seen so far in sorted order. For each new value, binary-search its insertion index and insert it there, then read the median from the middle position(s).

Why it's the natural first idea. It directly mirrors the definition — 'the median is the middle of the sorted values' — and gives O(1) median reads once the list is maintained.

Why it's too slow. Although finding the position is O(log n), physically inserting into a contiguous list shifts every element after it, costing O(n) per step and O(n²) overall. For n = 10⁵ that's ~10¹⁰ shifts — too slow. A balanced BST or skip list would make insertion O(log n), but that's more machinery than the two-heap trick, which needs no ordering of the whole sequence — only the boundary.

B · Visual dry run

Interactive dry run

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

stream = [12, 4, 5, 3, 8, 7]

Array state

after 3

[3,4,5,12], avg(4,5)

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result12.0 / 8.0 / 5.0 / 4.5 / 5.0 / 6.0

C · Code with teaching comments

Reference implementation previewpublic List<Double> runningMedian(int[] stream) { List<Integer> sorted = new ArrayList<>(); List<Double> medians = new ArrayList<>(); for (int x : stream) { int pos = Collections.binarySearch(sorted, x);Explore the full code

solution.javaJava

Brute Force — Insert into a Sorted List — reference

3 teaching notes

1
public List<Double> runningMedian(int[] stream) {
2
    List<Integer> sorted = new ArrayList<>();
3
    List<Double> medians = new ArrayList<>();
4
    for (int x : stream) {
5
        // Find the insertion index in O(log n); negative result encodes where it would
6
        // go.
7
        int pos = Collections.binarySearch(sorted, x);
8
        if (pos < 0) pos = -(pos + 1);
9
        // The O(n) part — inserting shifts every later element.
10
        sorted.add(pos, x);
11
        int m = sorted.size();
12
        double median;
13
        if (m % 2 == 1) {
14
            median = sorted.get(m / 2);
15
        } else {
16
            // Even count → average the two middle elements with floating division.
17
            median = (sorted.get(m / 2 - 1) + sorted.get(m / 2)) / 2.0;
18
        }
19
        medians.add(median);
20
    }
21
    return medians;
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²) timeO(n) spaceOpen the invariant and proofExplore the proof

We don't actually need the entire sequence sorted — we only need the one or two elements at the median boundary. Maintaining full sorted order is overkill; two heaps maintain just the boundary in O(log n).

ComplexityO(n²) time, O(n) space — Binary search finds the insertion point in O(log n), but inserting into an array shifts up to n elements → O(n) per insertion, O(n²) over the whole stream. Median lookup itself is O(1).

E · Edge cases and pitfalls4stream = [5] — Single element → 5.0; odd count path.Explore edge cases

Edge cases handled

stream = [5]Single element → 5.0; odd count path.

Pitfalls

Integer-dividing the even-case median — drops the .5.
Assuming binary search makes insertion O(log n) — the array shift is still O(n).
Re-sorting the whole list each step (even worse: O(n² log n)).

03.2

Approach 2 of 2 · Optimal

Two Heaps — Max-Heap + Min-Heap (Optimal)

TimeO(n log n)SpaceO(n)

The expected answer — describe it as 'split the stream at the median with a max-heap and a min-heap'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only ever need the element(s) at the median boundary, not the whole sorted order. What structure gives O(1) access to the largest of a set, or the smallest?

2Hint 2Explore hint

Use a max-heap `lower` for the smaller half and a min-heap `upper` for the larger half. New value: if it's ≤ lower's top, it belongs in the lower half, else the upper.

3Hint 3Explore hint

After inserting, if the heaps' sizes differ by more than one, move the top of the bigger heap to the other. Median = lower.top (odd) or average of both tops (even).

A · Core idea

Split the numbers into a smaller half (lower, a max-heap) and a larger half (upper, a min-heap). The largest of the small half (lower.top) and the smallest of the large half (upper.top) straddle the median.

Routing a new value. If lower is empty or x <= lower.top, x belongs in the small half → push to lower; otherwise push to upper. This keeps every element in lower ≤ every element in upper.

Rebalancing. After the push, one heap may be two elements ahead. Restore the invariant len(lower) == len(upper) or len(lower) == len(upper) + 1: if lower is more than one ahead, pop its max and push onto upper; if upper is ahead at all, pop its min and push onto lower. We deliberately let lower carry the extra element on odd counts so the odd-median is simply lower.top.

Reading the median. If the counts are equal, the two middle elements are exactly the two tops, so the median is (lower.top + upper.top) / 2.0. If lower has one more, the single middle element is lower.top. Both are O(1).

Why two heaps beat a sorted list. A heap gives O(1) access to just the boundary element we need and O(log n) insertion, instead of paying O(n) to keep the whole sequence ordered. We never need the full order — only the median boundary.

Language notes. Java's PriorityQueue is a min-heap; build the max-heap with new PriorityQueue<>(Collections.reverseOrder()). Python's heapq is min-only, so implement the max-heap by pushing negated values and negating on peek.

B · Visual dry run

Interactive dry run

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

stream = [12, 4, 5, 3, 8, 7]

Array state

balanced

lower=[4,3], upper=[5,12] → (4+5)/2

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result12.0 / 8.0 / 5.0 / 4.5 / 5.0 / 6.0

C · Code with teaching comments

solution.javaJava

Two Heaps — Max-Heap + Min-Heap (Optimal) — optimal

5 teaching notes

1
public List<Double> runningMedian(int[] stream) {
2
    PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
3
    PriorityQueue<Integer> upper = new PriorityQueue<>();                            // min-heap
4
    List<Double> medians = new ArrayList<>();
5
    for (int x : stream) {
6
        // Route x to the small half when it's not greater than the current small-half
7
        // maximum.
8
        if (lower.isEmpty() || x <= lower.peek()) {
9
            lower.offer(x);
10
        } else {
11
            upper.offer(x);
12
        }
13
        if (lower.size() > upper.size() + 1) {
14
            upper.offer(lower.poll());
15
        } else if (upper.size() > lower.size()) {
16
            lower.offer(upper.poll());
17
        }
18
        double median;
19
        if (lower.size() == upper.size()) {
20
            // Equal sizes → the two tops are the two middles; /2.0 keeps the .5.
21
            median = (lower.peek() + upper.peek()) / 2.0;
22
        } else {
23
            // Odd count → lower holds the extra element, so its top IS the median.
24
            median = lower.peek();
25
        }
26
        medians.add(median);
27
    }
28
    return medians;
29
}

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

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The median is a moving boundary; two heaps keep that boundary materialised as their tops at all times. The general technique — 'maintain two balanced heaps around a pivot statistic' — also solves Sliding Window Median and IPO/most-profit scheduling.

ComplexityO(n log n) time, O(n) space — Each insertion does O(1) heap peeks and at most a constant number of O(log n) pushes/pops (insert + one rebalance move), so O(log n) per element and O(n log n) for the stream. The two heaps store all n elements → O(n) space. Median read is O(1).

E · Edge cases and pitfalls8stream = [1, 2, 3, 4, 5] — Medians 1.0, 1.5, 2.0, 2.5, 3.0 — alternating odd/even correctly handled.Explore edge cases

Edge cases handled

stream = [1, 2, 3, 4, 5]Medians 1.0, 1.5, 2.0, 2.5, 3.0 — alternating odd/even correctly handled.
stream = [5, 5, 5]Duplicates route into lower (x <= top) and rebalance → medians 5.0, 5.0, 5.0.
stream = [0]lower empty → push 0; odd count → median 0.0 (zero is a valid value).

Pitfalls

Letting heap sizes drift apart — rebalance after every insertion.
Reading the wrong heap's top, or averaging when the count is odd.
Integer division on the even-case median — must use 2.0 / float.
Forgetting Python's heapq is min-only — negate values for the max-heap.
Comparing x to the wrong heap when routing (compare to lower's max).

Practice

Try the solution yourself

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

Editable code previewpublic List<Double> runningMedian(int[] stream) { PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap List<Double> medians = new ArrayList<>(); for (int x : stream) {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.

Integer division on the even median

Averaging the two middle values with integer division truncates: (4 + 5) / 2 = 4 instead of 4.5.

Explore the code comparison

Don't write this

median = (lower.peek() + upper.peek()) / 2;     // int division → 4

Write this instead

median = (lower.peek() + upper.peek()) / 2.0;   // double → 4.5

Not negating for Python's max-heap

heapq is min-only. Pushing raw values makes `lower` a min-heap, so lower[0] is the smallest of the small half — the routing comparison and median are then wrong.

Explore the code comparison

Don't write this

heapq.heappush(lower, x)
# ... compare x <= lower[0]  (lower[0] is the MIN, not the max)

Write this instead

heapq.heappush(lower, -x)
# ... compare x <= -lower[0]  (-lower[0] is the true max)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two heaps straddling the median (max-heap lower half, min-heap upper half)

Code pattern to memorize

if lower empty or x <= lower.top: lower.push(x)   # max-heap
else: upper.push(x)                                  # min-heap
rebalance so |len(lower) - len(upper)| <= 1, lower never smaller
median = lower.top                if len(lower) > len(upper)
       = (lower.top + upper.top)/2 if equal

Rules to remember

1lower is a max-heap (its top is the largest of the small half); upper is a min-heap (its top is the smallest of the large half). The median sits between the two tops.
2Keep the invariant len(lower) == len(upper) or len(lower) == len(upper) + 1 — let lower hold the extra element on odd counts.
3Rebalance every insertion: if one heap gets 2 ahead, move its top to the other heap.
4Median is `lower.top` on odd count, `(lower.top + upper.top) / 2.0` on even count — use floating division and print one decimal.
5In Java use PriorityQueue with Collections.reverseOrder() for the max-heap; in Python negate values for the max-heap since heapq is a min-heap only.

Use this pattern when

Median (or any percentile near the middle) of a growing stream
Repeated 'middle element' queries while elements keep arriving
Balancing two halves so both extremes are O(1) to read
Sliding-window median (with lazy deletion added)

Choose another pattern when

Whole array is known upfront and you query the median once → nth_element / quickselect in O(n)
You need arbitrary order statistics, not just the median → an order-statistics BST / Fenwick tree
Values are bounded small integers → a counting/Fenwick approach can give O(log range)

Interview takeaway

Two heaps keep a stream split at the median so both middle elements are always one peek away. 'Balance two heaps around a pivot quantity' is the go-to streaming-statistic pattern.

Continue

Transfer the pattern to another problem

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

Transferable patternTwo heaps. A max-heap (lower half) and min-heap (upper half) keep a stream split at the median, giving O(log n) insert and O(1) median. The same balance-two-heaps idea powers Sliding Window Median and Find Median from Data Stream.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sliding Window Median (LeetCode 480)
Coming soon
Same two heaps plus lazy deletion to evict the element leaving the window.
Find Median from Data Stream (LeetCode 295)
The identical two-heap structure as a class with addNum / findMedian methods.
IPO / Maximize Capital (LeetCode 502)
Two heaps again — one for affordable projects, one for the rest, balanced by capital.

Same pattern

←

Kth Largest Element in an Array

hardHeapFrequently asked

Find the Running Median

Heap & Priority Queue · 9 of 9 · 11 min

Numbers arrive one at a time. After reading each number, print the median of all numbers seen so far.

If the count of numbers seen is odd, the median is the middle element of the sorted sequence. If it is even, the median is the average of the two middle elements.

Print each median on its own line, formatted to one decimal place.

In plain English

Examples

Example 1

Input: stream = [12, 4, 5, 3, 8, 7]
Output: 12.0 8.0 5.0 4.5 5.0 6.0
Note: After 12 → 12.0. After 12,4 → (4+12)/2 = 8.0. After +5 → middle of [4,5,12] = 5.0. After +3 → ([3,4,5,12]) (4+5)/2 = 4.5. After +8 → middle of [3,4,5,8,12] = 5.0. After +7 → ([3,4,5,7,8,12]) (5+7)/2 = 6.0.

Example 2

Input: stream = [1, 2, 3, 4, 5]
Output: 1.0 1.5 2.0 2.5 3.0
Note: Sorted prefixes [1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5] give medians 1.0, 1.5, 2.0, 2.5, 3.0.

Constraints

1 ≤ n ≤ 10⁵ (numbers in the stream)
0 ≤ arr[i] ≤ 10⁵
Print each running median to exactly one decimal place
Median of an even count is the average of the two middle values (may end in .5)

Clarifying questions4First question: Do I report the median after every insertion or only once?Explore questions

Q1.Do I report the median after every insertion or only once?
After every insertion — that's why an incremental structure (two heaps) beats re-sorting.
Q2.How is the even-count median defined?
The average of the two middle elements, so it can be a .5 value — use floating-point division.
Q3.What output format is expected?
Each median on its own line, formatted to one decimal place (e.g. 8.0, 4.5).
Q4.Can numbers repeat or be zero?
Yes. Duplicates and zeros are ordinary values; the comparison with the max-heap top still routes them correctly.

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 reach for two heaps to get O(log n) insertion with O(1) median, and whether you get the rebalancing invariant and even/odd median formula exactly right.

Where candidates slip

Letting the heap sizes drift apart, reading the wrong heap's top, integer-dividing the even-case median (losing the .5), or mixing up which heap is max vs min.

How to stand out

State the size invariant precisely, explain why the two tops bracket the median, and mention the language-specific max-heap trick (reverseOrder in Java, negation in Python).

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	Brute Force — Insert into a Sorted List	`O(n²)`	`O(n)`	State first to frame the cost; it's the obvious incremental idea before heaps.	Read
2	Two Heaps — Max-Heap + Min-Heap (Optimal)Optimal	`O(n log n)`	`O(n)`	The expected answer — describe it as 'split the stream at the median with a max-heap and a min-heap'.	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

Brute Force — Insert into a Sorted List

TimeO(n²)SpaceO(n)

State first to frame the cost; it's the obvious incremental idea before heaps.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you kept the numbers seen so far in sorted order, where is the median?

2Hint 2Explore hint

Maintain a sorted list. Insert each new value in its correct position (binary search to find it, but the shift is the costly part).

3Hint 3Explore hint

Median is then the middle element (or average of the two middle) — O(1) to read, but each insertion shifts elements in O(n).

A · Core idea

Keep a list of all values seen so far in sorted order. For each new value, binary-search its insertion index and insert it there, then read the median from the middle position(s).

Why it's the natural first idea. It directly mirrors the definition — 'the median is the middle of the sorted values' — and gives O(1) median reads once the list is maintained.

B · Visual dry run

Interactive dry run

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

stream = [12, 4, 5, 3, 8, 7]

Array state

after 3

[3,4,5,12], avg(4,5)

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result12.0 / 8.0 / 5.0 / 4.5 / 5.0 / 6.0

C · Code with teaching comments

solution.javaJava

Brute Force — Insert into a Sorted List — reference

3 teaching notes

1
public List<Double> runningMedian(int[] stream) {
2
    List<Integer> sorted = new ArrayList<>();
3
    List<Double> medians = new ArrayList<>();
4
    for (int x : stream) {
5
        // Find the insertion index in O(log n); negative result encodes where it would
6
        // go.
7
        int pos = Collections.binarySearch(sorted, x);
8
        if (pos < 0) pos = -(pos + 1);
9
        // The O(n) part — inserting shifts every later element.
10
        sorted.add(pos, x);
11
        int m = sorted.size();
12
        double median;
13
        if (m % 2 == 1) {
14
            median = sorted.get(m / 2);
15
        } else {
16
            // Even count → average the two middle elements with floating division.
17
            median = (sorted.get(m / 2 - 1) + sorted.get(m / 2)) / 2.0;
18
        }
19
        medians.add(median);
20
    }
21
    return medians;
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²) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4stream = [5] — Single element → 5.0; odd count path.Explore edge cases

Edge cases handled

stream = [5]Single element → 5.0; odd count path.

Pitfalls

Integer-dividing the even-case median — drops the .5.
Assuming binary search makes insertion O(log n) — the array shift is still O(n).
Re-sorting the whole list each step (even worse: O(n² log n)).

03.2

Approach 2 of 2 · Optimal

Two Heaps — Max-Heap + Min-Heap (Optimal)

TimeO(n log n)SpaceO(n)

The expected answer — describe it as 'split the stream at the median with a max-heap and a min-heap'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only ever need the element(s) at the median boundary, not the whole sorted order. What structure gives O(1) access to the largest of a set, or the smallest?

2Hint 2Explore hint

Use a max-heap `lower` for the smaller half and a min-heap `upper` for the larger half. New value: if it's ≤ lower's top, it belongs in the lower half, else the upper.

3Hint 3Explore hint

After inserting, if the heaps' sizes differ by more than one, move the top of the bigger heap to the other. Median = lower.top (odd) or average of both tops (even).

A · Core idea

B · Visual dry run

Interactive dry run

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

stream = [12, 4, 5, 3, 8, 7]

Array state

balanced

lower=[4,3], upper=[5,12] → (4+5)/2

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result12.0 / 8.0 / 5.0 / 4.5 / 5.0 / 6.0

C · Code with teaching comments

solution.javaJava

Two Heaps — Max-Heap + Min-Heap (Optimal) — optimal

5 teaching notes

1
public List<Double> runningMedian(int[] stream) {
2
    PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
3
    PriorityQueue<Integer> upper = new PriorityQueue<>();                            // min-heap
4
    List<Double> medians = new ArrayList<>();
5
    for (int x : stream) {
6
        // Route x to the small half when it's not greater than the current small-half
7
        // maximum.
8
        if (lower.isEmpty() || x <= lower.peek()) {
9
            lower.offer(x);
10
        } else {
11
            upper.offer(x);
12
        }
13
        if (lower.size() > upper.size() + 1) {
14
            upper.offer(lower.poll());
15
        } else if (upper.size() > lower.size()) {
16
            lower.offer(upper.poll());
17
        }
18
        double median;
19
        if (lower.size() == upper.size()) {
20
            // Equal sizes → the two tops are the two middles; /2.0 keeps the .5.
21
            median = (lower.peek() + upper.peek()) / 2.0;
22
        } else {
23
            // Odd count → lower holds the extra element, so its top IS the median.
24
            median = lower.peek();
25
        }
26
        medians.add(median);
27
    }
28
    return medians;
29
}

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

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8stream = [1, 2, 3, 4, 5] — Medians 1.0, 1.5, 2.0, 2.5, 3.0 — alternating odd/even correctly handled.Explore edge cases

Edge cases handled

stream = [1, 2, 3, 4, 5]Medians 1.0, 1.5, 2.0, 2.5, 3.0 — alternating odd/even correctly handled.
stream = [5, 5, 5]Duplicates route into lower (x <= top) and rebalance → medians 5.0, 5.0, 5.0.
stream = [0]lower empty → push 0; odd count → median 0.0 (zero is a valid value).

Pitfalls

Letting heap sizes drift apart — rebalance after every insertion.
Reading the wrong heap's top, or averaging when the count is odd.
Integer division on the even-case median — must use 2.0 / float.
Forgetting Python's heapq is min-only — negate values for the max-heap.
Comparing x to the wrong heap when routing (compare to lower's max).

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.

Integer division on the even median

Averaging the two middle values with integer division truncates: (4 + 5) / 2 = 4 instead of 4.5.

Explore the code comparison

Don't write this

median = (lower.peek() + upper.peek()) / 2;     // int division → 4

Write this instead

median = (lower.peek() + upper.peek()) / 2.0;   // double → 4.5

Not negating for Python's max-heap

heapq is min-only. Pushing raw values makes `lower` a min-heap, so lower[0] is the smallest of the small half — the routing comparison and median are then wrong.

Explore the code comparison

Don't write this

heapq.heappush(lower, x)
# ... compare x <= lower[0]  (lower[0] is the MIN, not the max)

Write this instead

heapq.heappush(lower, -x)
# ... compare x <= -lower[0]  (-lower[0] is the true max)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two heaps straddling the median (max-heap lower half, min-heap upper half)

Code pattern to memorize

if lower empty or x <= lower.top: lower.push(x)   # max-heap
else: upper.push(x)                                  # min-heap
rebalance so |len(lower) - len(upper)| <= 1, lower never smaller
median = lower.top                if len(lower) > len(upper)
       = (lower.top + upper.top)/2 if equal

Rules to remember

1lower is a max-heap (its top is the largest of the small half); upper is a min-heap (its top is the smallest of the large half). The median sits between the two tops.
2Keep the invariant len(lower) == len(upper) or len(lower) == len(upper) + 1 — let lower hold the extra element on odd counts.
3Rebalance every insertion: if one heap gets 2 ahead, move its top to the other heap.
4Median is `lower.top` on odd count, `(lower.top + upper.top) / 2.0` on even count — use floating division and print one decimal.
5In Java use PriorityQueue with Collections.reverseOrder() for the max-heap; in Python negate values for the max-heap since heapq is a min-heap only.

Use this pattern when

Median (or any percentile near the middle) of a growing stream
Repeated 'middle element' queries while elements keep arriving
Balancing two halves so both extremes are O(1) to read
Sliding-window median (with lazy deletion added)

Choose another pattern when

Whole array is known upfront and you query the median once → nth_element / quickselect in O(n)
You need arbitrary order statistics, not just the median → an order-statistics BST / Fenwick tree
Values are bounded small integers → a counting/Fenwick approach can give O(log range)

Interview takeaway

Two heaps keep a stream split at the median so both middle elements are always one peek away. 'Balance two heaps around a pivot quantity' is the go-to streaming-statistic pattern.

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 (LeetCode 480)
Coming soon
Same two heaps plus lazy deletion to evict the element leaving the window.
Find Median from Data Stream (LeetCode 295)
The identical two-heap structure as a class with addNum / findMedian methods.
IPO / Maximize Capital (LeetCode 502)
Two heaps again — one for affordable projects, one for the rest, balanced by capital.

Same pattern

←

Kth Largest Element in an Array