DSA-073 · FOCUSED PRACTICE
Find Median from Data Stream
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 154641 deterministic checks. Learner drafts are not executed.
Understand the problem
Implement a MedianFinder with add(int), median(), and size(). Retain every occurrence from an insert-only int stream and return the exact current median without sorting all history on each read.
- Each instance begins empty and receives at most 100,000 inserted ints, including duplicates and extremes. add is void; size returns the total occurrence count. The object is mutable, per-instance, and not thread-safe.
- median returns double: the middle occurrence when odd, or the mean of the two middle values when even. On empty input it throws NoSuchElementException without changing state. Repeated median/size calls do not consume values.
- Maintain a lower max-heap and upper min-heap. At public operation boundaries every lower value is <= every upper value, and lower has the same size as upper or one extra. Reverse ordering must not negate MIN, and even averaging widens before addition. Trace null denotes a void add outcome, not a returned null.
Examples
Input:
add 5, add 1, add 9, add 2; median after each
Output:5.0,3.0,5.0,3.5The two roots supply the central pair while each insertion repairs size balance.
Input:
add MIN, add MAX; median
Output:−0.5Long addition avoids int overflow and /2.0 avoids truncation.
Input:
median on a new instance
Output:NoSuchElementException; size remains 0No numeric sentinel can represent every valid median plus absence.
Before you start
- Median as a rank boundary (DSA-068)
- Heap roots, size balance, and widened averaging
Recognize the structure
The median needs only the boundary between lower and upper ranks. Keep every lower-half value in a max-heap and every upper-half value in a min-heap, so roots expose the two central candidates. This differs from an approximate quantile summary and requires linear history storage for the exact insert-only structure.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 121/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Can the two central ranks be exposed without sorting all values?
Hint 2
Keep a max-heap below the median and a min-heap above it.
Hint 3
Route by the lower root, transfer one boundary root if sizes differ incorrectly, then peek the middle value(s).
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Maintain a sorted list by indexed insertion
Binary-search an insertion position in an ArrayList and shift the suffix to insert. Median then reads one or two middle entries. Inserting 5,1,9,2 produces [5], [1,5], [1,5,9], [1,2,5,9], with medians 5,3,5,3.5. Lookup of the position is logarithmic, but shifting makes insertion O(m) at stream size m; median is O(1) and storage O(m).
Improve the baseline
Choose a side without breaking rank order
If lower is empty or value<=lower.peek(), insert into lower; otherwise insert into upper. This preserves lower<=upper ordering, but one side may temporarily become too large.
Move only a bordering root
If lower exceeds upper by more than one, move lower’s maximum to upper. If upper is larger, move its minimum to lower. One transfer suffices after a single insertion, and the moved boundary value preserves cross-heap order.
Read the central rank boundary
With odd size the extra lower root is the middle occurrence. With equal sizes, lower.peek() and upper.peek() are the two middle occurrences. Return their widened average without removing either root.
Why it is correct
Order invariant
Insertion is routed relative to the greatest lower value. A value sent lower is no larger than the old lower maximum, which is <= every upper value; a value sent upper exceeds that maximum. Moving the maximum lower or minimum upper across the boundary preserves all cross inequalities.
Size invariant
Before add, lower−upper size is zero or one. One insertion changes it by at most one, so a single transfer restores difference zero or one. This invariant is guaranteed after the complete add, not necessarily immediately after offer.
Median and query purity
The ordered halves and their balanced sizes identify the exact middle rank(s), including repeated values. peek and size do not mutate queues; an empty exception is checked before reading a root. Thus reads preserve future insertion behavior.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
public final class Solution {
public static final class MedianFinder {
private final PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder());
private final PriorityQueue<Integer> upper = new PriorityQueue<>();
public void add(int value) {
if (lower.isEmpty() || value <= lower.peek()) lower.offer(value);
else upper.offer(value);
if (lower.size() > upper.size() + 1) upper.offer(lower.poll());
else if (upper.size() > lower.size()) lower.offer(upper.poll());
}
public double median() {
if (lower.isEmpty()) throw new NoSuchElementException("empty stream");
return lower.size() > upper.size() ? lower.peek() : ((long) lower.peek() + upper.peek()) / 2.0;
}
public int size() { return lower.size() + upper.size(); }
}
public static final class Baseline {
private final ArrayList<Integer> sorted = new ArrayList<>();
public void add(int value) {
int at = Collections.binarySearch(sorted,value);
sorted.add(at < 0 ? -at - 1 : at,value);
}
public double median() {
if (sorted.isEmpty()) throw new NoSuchElementException("empty stream");
int mid = sorted.size() / 2;
return sorted.size() % 2 == 1 ? sorted.get(mid) : ((long) sorted.get(mid-1) + sorted.get(mid)) / 2.0;
}
public int size() { return sorted.size(); }
}
}
Read the meaningful blocks
Safe lower max-heap
Comparator.reverseOrder() reverses comparisons without negating values, which would overflow for MIN.
Rebalance at most once
The two conditions encode lower-owning-the-extra convention. Different conventions are valid only with matching read logic.
Widen before averaging
((long)lower.peek()+upper.peek())/2.0 adds exact int values in long, then produces an exact integer or half-integer double.
Complexity
At size m, add performs O(log(m+1)) heap work, median and size take O(1), and retained storage is O(m). A logarithmic insertion bound includes constant work for an empty or singleton stream.
The sorted-list baseline uses O(m) insertion due to shifts, O(1) queries, and O(m) storage. Re-sorting all history on every query would instead add O(m log(m+1)) read cost.
Exact-state walkthroughs
Reveal normal and boundary traces
Insertion, balancing, and empty/read outcomes
Input: {"operations":[["median"],["add",5],["add",1],["median"],["add",9],["median"],["add",2],["median"],["size"]]} · Operation outcomes: ["NoSuchElementException",null,null,3,null,5,null,3.5,4]
Step 1 of 15: Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
Phase: initial. Total occurrences: 0.
Lower half — maximum/root first
Empty.
Upper half — minimum/root first
Empty.
At an operation boundary, lower has equal size or one extra and every lower value is <= every upper value.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lowerValues | [] |
| upperValues | [] |
| outcomes | [] |
| phase | "initial" |
| size | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.Comparator; 4 import java.util.NoSuchElementException; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class MedianFinder { 8 private final PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder()); 9 private final PriorityQueue<Integer> upper = new PriorityQueue<>(); 10 public void add(int value) { 11 if (lower.isEmpty() || value <= lower.peek()) lower.offer(value); 12 else upper.offer(value); 13 if (lower.size() > upper.size() + 1) upper.offer(lower.poll()); 14 else if (upper.size() > lower.size()) lower.offer(upper.poll()); 15 } 16 public double median() { 17 if (lower.isEmpty()) throw new NoSuchElementException("empty stream"); 18 return lower.size() > upper.size() ? lower.peek() : ((long) lower.peek() + upper.peek()) / 2.0; 19 } 20 public int size() { return lower.size() + upper.size(); } 21 } 22 public static final class Baseline { 23 private final ArrayList<Integer> sorted = new ArrayList<>(); 24 public void add(int value) { 25 int at = Collections.binarySearch(sorted,value); 26 sorted.add(at < 0 ? -at - 1 : at,value); 27 } 28 public double median() { 29 if (sorted.isEmpty()) throw new NoSuchElementException("empty stream"); 30 int mid = sorted.size() / 2; 31 return sorted.size() % 2 == 1 ? sorted.get(mid) : ((long) sorted.get(mid-1) + sorted.get(mid)) / 2.0; 32 } 33 public int size() { return sorted.size(); } 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
- lowerValues
[]- upperValues
[]- outcomes
[]- phase
"initial"- size
0
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[]- upperValues
[]- outcomes
["NoSuchElementException"]- phase
"query"- index
0- operation
"median"- outcome
"NoSuchElementException"- size
0
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[5]- upperValues
[]- outcomes
["NoSuchElementException"]- phase
"inserted"- index
1- operation
"add"- value
5- side
"lower"- size
1
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[5]- upperValues
[]- outcomes
["NoSuchElementException",null]- phase
"stable"- index
1- operation
"add"- value
5- transfer
null- size
1- outcome
null
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[5,1]- upperValues
[]- outcomes
["NoSuchElementException",null]- phase
"inserted"- index
2- operation
"add"- value
1- side
"lower"- size
2
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[1]- upperValues
[5]- outcomes
["NoSuchElementException",null,null]- phase
"stable"- index
2- operation
"add"- value
1- transfer
"lower-to-upper"- size
2- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[1]- upperValues
[5]- outcomes
["NoSuchElementException",null,null,3]- phase
"query"- index
3- operation
"median"- outcome
3- size
2
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[1]- upperValues
[5,9]- outcomes
["NoSuchElementException",null,null,3]- phase
"inserted"- index
4- operation
"add"- value
9- side
"upper"- size
3
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[5,1]- upperValues
[9]- outcomes
["NoSuchElementException",null,null,3,null]- phase
"stable"- index
4- operation
"add"- value
9- transfer
"upper-to-lower"- size
3- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[5,1]- upperValues
[9]- outcomes
["NoSuchElementException",null,null,3,null,5]- phase
"query"- index
5- operation
"median"- outcome
5- size
3
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[5,2,1]- upperValues
[9]- outcomes
["NoSuchElementException",null,null,3,null,5]- phase
"inserted"- index
6- operation
"add"- value
2- side
"lower"- size
4
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[2,1]- upperValues
[5,9]- outcomes
["NoSuchElementException",null,null,3,null,5,null]- phase
"stable"- index
6- operation
"add"- value
2- transfer
"lower-to-upper"- size
4- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[2,1]- upperValues
[5,9]- outcomes
["NoSuchElementException",null,null,3,null,5,null,3.5]- phase
"query"- index
7- operation
"median"- outcome
3.5- size
4
- Read size without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[2,1]- upperValues
[5,9]- outcomes
["NoSuchElementException",null,null,3,null,5,null,3.5,4]- phase
"query"- index
8- operation
"size"- outcome
4- size
4
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
["NoSuchElementException",null,null,3,null,5,null,3.5,4]
Extreme values yield an exact negative half
Input: {"operations":[["add",-2147483648],["median"],["add",2147483647],["median"],["add",2147483647],["median"]]} · Operation outcomes: [null,-2147483648,null,-0.5,null,2147483647]
Step 1 of 11: Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
Phase: initial. Total occurrences: 0.
Lower half — maximum/root first
Empty.
Upper half — minimum/root first
Empty.
At an operation boundary, lower has equal size or one extra and every lower value is <= every upper value.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lowerValues | [] |
| upperValues | [] |
| outcomes | [] |
| phase | "initial" |
| size | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.Comparator; 4 import java.util.NoSuchElementException; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class MedianFinder { 8 private final PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder()); 9 private final PriorityQueue<Integer> upper = new PriorityQueue<>(); 10 public void add(int value) { 11 if (lower.isEmpty() || value <= lower.peek()) lower.offer(value); 12 else upper.offer(value); 13 if (lower.size() > upper.size() + 1) upper.offer(lower.poll()); 14 else if (upper.size() > lower.size()) lower.offer(upper.poll()); 15 } 16 public double median() { 17 if (lower.isEmpty()) throw new NoSuchElementException("empty stream"); 18 return lower.size() > upper.size() ? lower.peek() : ((long) lower.peek() + upper.peek()) / 2.0; 19 } 20 public int size() { return lower.size() + upper.size(); } 21 } 22 public static final class Baseline { 23 private final ArrayList<Integer> sorted = new ArrayList<>(); 24 public void add(int value) { 25 int at = Collections.binarySearch(sorted,value); 26 sorted.add(at < 0 ? -at - 1 : at,value); 27 } 28 public double median() { 29 if (sorted.isEmpty()) throw new NoSuchElementException("empty stream"); 30 int mid = sorted.size() / 2; 31 return sorted.size() % 2 == 1 ? sorted.get(mid) : ((long) sorted.get(mid-1) + sorted.get(mid)) / 2.0; 32 } 33 public int size() { return sorted.size(); } 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
- lowerValues
[]- upperValues
[]- outcomes
[]- phase
"initial"- size
0
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[-2147483648]- upperValues
[]- outcomes
[]- phase
"inserted"- index
0- operation
"add"- value
-2147483648- side
"lower"- size
1
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[-2147483648]- upperValues
[]- outcomes
[null]- phase
"stable"- index
0- operation
"add"- value
-2147483648- transfer
null- size
1- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[-2147483648]- upperValues
[]- outcomes
[null,-2147483648]- phase
"query"- index
1- operation
"median"- outcome
-2147483648- size
1
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[-2147483648]- upperValues
[2147483647]- outcomes
[null,-2147483648]- phase
"inserted"- index
2- operation
"add"- value
2147483647- side
"upper"- size
2
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[-2147483648]- upperValues
[2147483647]- outcomes
[null,-2147483648,null]- phase
"stable"- index
2- operation
"add"- value
2147483647- transfer
null- size
2- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[-2147483648]- upperValues
[2147483647]- outcomes
[null,-2147483648,null,-0.5]- phase
"query"- index
3- operation
"median"- outcome
-0.5- size
2
- Insert on the ordered side before repairing sizes.
Cross-half value order holds, but the size difference may temporarily be two or upper may have one extra.
- lowerValues
[-2147483648]- upperValues
[2147483647,2147483647]- outcomes
[null,-2147483648,null,-0.5]- phase
"inserted"- index
4- operation
"add"- value
2147483647- side
"upper"- size
3
- Repair the size convention and complete the void add.
lower has equal size or one extra, with every lower value <= every upper value. null labels a void outcome, not a returned null.
- lowerValues
[2147483647,-2147483648]- upperValues
[2147483647]- outcomes
[null,-2147483648,null,-0.5,null]- phase
"stable"- index
4- operation
"add"- value
2147483647- transfer
"upper-to-lower"- size
3- outcome
null
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[2147483647,-2147483648]- upperValues
[2147483647]- outcomes
[null,-2147483648,null,-0.5,null,2147483647]- phase
"query"- index
5- operation
"median"- outcome
2147483647- size
3
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[null,-2147483648,null,-0.5,null,2147483647]
Read-only operations on an empty instance
Input: {"operations":[["size"],["median"]]} · Operation outcomes: [0,"NoSuchElementException"]
Step 1 of 4: Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
Phase: initial. Total occurrences: 0.
Lower half — maximum/root first
Empty.
Upper half — minimum/root first
Empty.
At an operation boundary, lower has equal size or one extra and every lower value is <= every upper value.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| lowerValues | [] |
| upperValues | [] |
| outcomes | [] |
| phase | "initial" |
| size | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.Comparator; 4 import java.util.NoSuchElementException; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class MedianFinder { 8 private final PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder()); 9 private final PriorityQueue<Integer> upper = new PriorityQueue<>(); 10 public void add(int value) { 11 if (lower.isEmpty() || value <= lower.peek()) lower.offer(value); 12 else upper.offer(value); 13 if (lower.size() > upper.size() + 1) upper.offer(lower.poll()); 14 else if (upper.size() > lower.size()) lower.offer(upper.poll()); 15 } 16 public double median() { 17 if (lower.isEmpty()) throw new NoSuchElementException("empty stream"); 18 return lower.size() > upper.size() ? lower.peek() : ((long) lower.peek() + upper.peek()) / 2.0; 19 } 20 public int size() { return lower.size() + upper.size(); } 21 } 22 public static final class Baseline { 23 private final ArrayList<Integer> sorted = new ArrayList<>(); 24 public void add(int value) { 25 int at = Collections.binarySearch(sorted,value); 26 sorted.add(at < 0 ? -at - 1 : at,value); 27 } 28 public double median() { 29 if (sorted.isEmpty()) throw new NoSuchElementException("empty stream"); 30 int mid = sorted.size() / 2; 31 return sorted.size() % 2 == 1 ? sorted.get(mid) : ((long) sorted.get(mid-1) + sorted.get(mid)) / 2.0; 32 } 33 public int size() { return sorted.size(); } 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create an empty exact median instance.
Lower is max-priority first and upper min-priority first. Display order is sorted logical contents, not heap storage.
- lowerValues
[]- upperValues
[]- outcomes
[]- phase
"initial"- size
0
- Read size without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[]- upperValues
[]- outcomes
[0]- phase
"query"- index
0- operation
"size"- outcome
0- size
0
- Read median without consuming stream data.
Queries preserve both heaps and their public invariants; empty median is a thrown outcome label.
- lowerValues
[]- upperValues
[]- outcomes
[0,"NoSuchElementException"]- phase
"query"- index
1- operation
"median"- outcome
"NoSuchElementException"- size
0
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[0,"NoSuchElementException"]
Test the contract
Input:
Empty median query
Output:NoSuchElementException; size 0Absence is not a numeric sentinel.
Input:
5,1,9,2
Output:Medians 5,3,5,3.5Both rebalance directions.
Input:
MIN,MAX
Output:−0.5Signed boundaries.
Input:
Repeated equal values
Output:Same median, increasing sizeOccurrence multiplicity.
Input:
100,000 increasing inserts
Output:Median (last value)/2 after each insertStateful size/ordering boundary.
Common mistakes and counterexamples
Store negatives to emulate a max-heap
Counterexample: Negating MIN leaves it unchanged and breaks ordering.
Use a reversed comparator.
Average int roots before converting
Counterexample: MAX+MAX overflows even if assigned afterward to double.
Widen an operand before the addition.
Assume heaps are globally sorted containers
Counterexample: Their iteration order does not identify the complete rank sequence.
Use only root/size guarantees; displays sort logical contents explicitly.
Claim balance immediately after offer
Counterexample: A lower insertion can temporarily produce a size difference of two.
Separate insertion and repair stages, asserting the public invariant after rebalance.
Follow-ups
Delete old values for a sliding median.
Two insert-only heaps cannot remove arbitrary expired occurrences efficiently. Add indexed deletion or carefully bounded lazy-deletion bookkeeping, preserve multiplicities, and distinguish logical size from physical heap size.
Approximate quantiles in bounded memory.
Use a quantile sketch with explicit error guarantees rather than claiming these exact heaps use constant memory. Exact unrestricted history and approximate summaries have different contracts.
Merge two MedianFinder instances.
Two median scalars alone cannot reconstruct the combined median. Retained distributions or all values must be combined; analyze rebuilding versus repeated insertions and preserve occurrence counts.