Definition
- Two-heap structure – a max-heap holds the lower half of the stream, a min-heap holds the upper half.
- Max-heap top – the largest value in the lower half, sitting at the boundary.
- Min-heap top – the smallest value in the upper half, the other boundary.
- Balance invariant – the max-heap has at most one more element than the min-heap.
- Median – odd count: max-heap top; even count: average of both tops.
- Complexity – O(log n) per add (constant heap ops), O(1) per median read.
At the National Bank of India, a monitoring service tracks the median transaction amount all day. Imagine two piles of coins: a low pile where the biggest coin sits on top, and a high pile where the smallest coin sits on top. The piles are kept nearly equal in height, so the median is right at the boundary between them.
Understanding the Concepts
What is the Find Median from Data Stream problem?
Design a data structure that supports two operations: add a number from a stream and return the median of all numbers added so far. The add must run in O(log n) time and the median read in O(1) time. Re-sorting the entire history on each add would be O(n log n), which is too slow.
package com.bank.service;
import java.util.PriorityQueue;
import java.util.Collections;
public class MedianFinder {
private PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
private PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap
public void addNum(int num) {
low.offer(num);
high.offer(low.poll());
if (high.size() > low.size()) {
low.offer(high.poll());
}
}
public double findMedian() {
if (low.size() > high.size()) {
return low.peek();
}
return (low.peek() + high.peek()) / 2.0;
}
}
How does the push-then-shift pattern work?
On each add, push the new value into the max-heap (low), then immediately move low's top to the min-heap (high). This ensures every element in low is no larger than every element in high. Then rebalance: if high grows larger than low, move high's top back to low.
package com.bank.service;
public class PushShiftDemo {
public static void main(String[] args) {
MedianFinder mf = new MedianFinder();
int[] stream = {5, 15, 1, 3};
for (int num : stream) {
mf.addNum(num);
System.out.println("Add " + num + ": median = " + mf.findMedian());
}
}
}
Add 5: median = 5.0
Add 15: median = 10.0
Add 1: median = 5.0
Add 3: median = 4.0
Why does this guarantee correct partitioning?
Pushing to low first and then shifting low's top to high ensures that the value that enters high is the maximum of the current low heap. This maintains the invariant that every element in low is at most equal to every element in high. The rebalance step ensures the size difference never exceeds one.
// Invariants maintained by push-then-shift:
// 1. max(low) <= min(high) (partition correctness)
// 2. low.size() == high.size() or low.size() == high.size() + 1
// (balance)
//
// These two invariants place the median at the boundary.
How do you read the median?
With an odd total count, the max-heap has one extra element, and its top is the median. With an even count, the two heaps have equal size, and the median is the average of both tops.
public double findMedian() {
if (low.size() > high.size()) {
return low.peek(); // odd count: low has the extra element
}
return (low.peek() + high.peek()) / 2.0; // even count: average
}
What is the time and space complexity?
Each add does at most three heap operations (push, poll, push), each O(log n). The median read peeks at most two tops, which is O(1). Space is O(n) for storing all elements.
- addNum – O(log n) per call.
- findMedian – O(1) per call.
- Space – O(n) total for all stored elements.
// Per addNum:
// low.offer(num) -> O(log n)
// high.offer(low.poll()) -> O(log n)
// if rebalance: low.offer(high.poll()) -> O(log n)
// Total: O(log n) per add
// Per findMedian:
// low.peek() and/or high.peek() -> O(1)
What are the edge cases?
Edge cases include a single element (median is that element), two elements (median is their average), all elements being the same, and very large or very small values that could cause overflow in the average.
package com.bank.service;
public class MedianEdgeCases {
public static void main(String[] args) {
MedianFinder mf = new MedianFinder();
// Single element
mf.addNum(42);
System.out.println(mf.findMedian()); // 42.0
// Two elements
mf.addNum(10);
System.out.println(mf.findMedian()); // 26.0
// Overflow-safe average: use long
// (Integer.MAX_VALUE + Integer.MAX_VALUE) / 2.0 is safe in double
}
}
42.0
26.0
What are common mistakes?
The most common mistake is not using the push-then-shift pattern and instead manually comparing against both tops, which is error-prone. Another mistake is inconsistently choosing which heap holds the extra element (should always be the max-heap for odd counts).
// WRONG: manual comparison (easy to get wrong)
if (num <= low.peek()) low.offer(num);
else high.offer(num);
// Then rebalance... but edge cases with empty heaps!
// CORRECT: push-then-shift (always correct)
low.offer(num);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
How is this different from using a sorted list?
A sorted list gives O(1) median read but O(n) insertion (shifting elements). The two-heap approach gives O(log n) insertion and O(1) median read, which is better for streaming data.
| Approach | Add | Median | Space |
|---|---|---|---|
| Sorted list | O(n) | O(1) | O(n) |
| Two heaps | O(log n) | O(1) | O(n) |
| Re-sort each time | O(n log n) | O(1) | O(n) |
// Sorted list: O(n) insert due to shifting
// Two heaps: O(log n) insert, O(1) median
// Clear winner for streaming data
How would you apply this in a banking system?
At the National Bank of India, a monitoring service reports the running median transaction amount as amounts stream in all day. Drift from the normal median triggers alerts for anomaly detection.
package com.bank.service;
public class TransactionMedianMonitor {
private final MedianFinder medianFinder = new MedianFinder();
private final double alertThreshold;
public TransactionMedianMonitor(double threshold) {
this.alertThreshold = threshold;
}
public void recordTransaction(int amountPaise) {
medianFinder.addNum(amountPaise);
double median = medianFinder.findMedian();
if (Math.abs(amountPaise - median) > alertThreshold) {
System.out.println("ALERT: amount " + amountPaise
+ " deviates from median " + median);
}
}
}
What should a senior engineer know?
A senior engineer should know the push-then-shift pattern guarantees correctness without manual top comparisons. They should also know about the follow-up: what if you need the median over only the last N elements (sliding window median), which requires a balanced BST or augmented heap with lazy deletion.
// Follow-up: sliding window median
// - Cannot simply remove from a heap in O(log n) without index
// - Options:
// 1. TreeMap with counts (balanced BST)
// 2. Two heaps with lazy deletion (mark deleted, skip on peek)
// 3. Order-statistic tree
Visual Overview
Stream: 5, 15, 1, 3
Add 5: low=[5] high=[] → median=5
Add 15: low=[5] high=[15] → median=(5+15)/2=10
Add 1: low=[1,5] high=[15] → median=5
(low: max-heap, top=5)
Add 3: low=[3,1] high=[5,15] → median=(3+5)/2=4
(low: max-heap, top=3; high: min-heap, top=5)
┌─────────────────────────────────────────────┐
│ Max-Heap (low) │ Min-Heap (high) │
│ top = largest low │ top = smallest high │
│ │ │
│ [3] │ [5] │
│ / \ │ / \ │
│ [1] │ [15] │
│ │ │
│ Median boundary: │ │
│ odd: low.peek() │ │
│ even: (3+5)/2 = 4 │ │
└─────────────────────────────────────────────┘
Key Takeaway
Find Median from Data Stream uses two heaps that split the data at the median: a max-heap for the lower half and a min-heap for the upper half. The max-heap's top is the largest small value and the min-heap's top is the smallest large value, placing the median right at the boundary.
On each add, I push to the max-heap, shift its top to the min-heap, and rebalance if needed. This push-then-shift pattern guarantees that every element in the lower heap is at most equal to every element in the upper heap, without manual comparisons against both tops. The median is the max-heap's top for odd counts, or the average of both tops for even counts.
Each add costs O(log n) for a constant number of heap operations, and the median read is O(1). The common mistake is manually comparing the new value against both tops instead of using the push-then-shift pattern. A senior engineer also knows the sliding-window median follow-up, which requires a balanced BST or lazy-deletion heaps.
At the National Bank of India, a monitoring service reported the running median transaction amount as amounts streamed in all day, triggering alerts when individual amounts deviated significantly from the median.
Remember one sentence: push to low, shift low's top to high, rebalance, and the median sits at the boundary of the two heaps.
---