Find Median from Data Stream

Learning goal: Understand why a stream of numbers needs a specialized structure instead of repeatedly sorting all values.

Core idea Numbers arrive one at a time, so the data structure must preserve enough order information for a fast median query. Sorting every value after each insertion would repeatedly redo work. The target is O(log n) for addNum() and O(1) for findMedian().

Algorithm plan

• Maintain a partition between the lower half and upper half of the values.
• Store the lower half in a max-heap so its largest value is immediately available.
• Store the upper half in a min-heap so its smallest value is immediately available.
• Rebalance after each insertion.
• Read one or two heap tops to calculate the median.

Micro-example For [1, 3, 5, 15], the lower half is [1, 3] and the upper half is [5, 15]. The two boundary values are 3 and 5, so the median is 4.

Pitfalls

• Treating either heap as a fully sorted array is unnecessary.
• Forgetting that the two heaps together contain every inserted number.
• Returning a single top when the total count is even.

Recap

• The median depends only on the boundary between two halves.
• Two heaps expose those boundaries efficiently.
• Balance is part of the data structure invariant.

Learning goal: See how two opposite heap orders make the median accessible.

Core idea Let low be a max-heap containing the smaller half and high be a min-heap containing the larger half. Every value in low must be less than or equal to every value in high. Because the heaps expose opposite extremes, low.top and high.top straddle the median.

Algorithm plan

• If low is empty or num <= low.top, insert into low.
• Otherwise insert into high.
• If low has more than one extra element, move low.top to high.
• If high is larger than low, move high.top to low.
• Use the larger heap's top for an odd count; average both tops for an even count.

Micro-example After inserting [1, 3, 5], low contains [3, 1] and high contains [5]. Since low has one extra item, low.top = 3 is the median.

Pitfalls

• A max-heap is required for low; a min-heap would expose the wrong boundary.
• A min-heap is required for high so its smallest upper value is visible.
• The ordering invariant and size invariant must both hold.

Recap

• low.top is the lower boundary.
• high.top is the upper boundary.
• Balanced sizes determine whether one top or two tops represent the median.

Learning goal: Translate the two-heap idea into a reliable insertion procedure.

Core idea Insertion has two stages: place the new value near its correct side, then repair the size balance. A heap insertion costs O(log n), and moving a root between heaps also costs O(log n). The rebalancing rules are simple because the allowed size difference is only one.

Algorithm plan

1. Compare num with low.top; choose low for smaller values and high otherwise.
2. If low.size > high.size + 1, move the maximum from low into high.
3. If high.size > low.size, move the minimum from high into low.
4. For an odd total, return low.top because low is allowed to have the extra value.
5. For an even total, return (low.top + high.top) / 2.

addNum(num):
    insert num into low or high
    if low has two more values than high:
        move low.top to high
    if high has more values than low:
        move high.top to low

Micro-example Insert 3 after [1, 5, 15]. It belongs in low, temporarily making low contain three values and high one. Moving low.top = 5 to high restores sizes 2 and 2.

Pitfalls

• Rebalance after every insertion, not only before a query.
• Move the correct root: maximum from low, minimum from high.
• Keep low as the heap allowed to contain the extra item.

Recap

• Insert, then rebalance.
• Each insertion remains logarithmic.
• The size convention makes odd-count handling deterministic.

Learning goal: Trace every insertion in one stream and connect heap changes to the returned median.

Core idea Use the example stream 5, 15, 1, 3. After every insertion, the max-heap low represents the lower half and the min-heap high represents the upper half. The heaps may have different internal arrangements, but their roots and sizes must satisfy the invariants.

Algorithm plan

• Insert 5 into low; it is the only value, so the median is 5.
• Insert 15 into high; equal sizes make the median (5 + 15) / 2 = 10.
• Insert 1 into low; its extra item makes low.top = 5 the median.
• Insert 3 into low; the size gap becomes two, so move 5 to high.
• The final boundary values are 3 and 5, producing median 4.

Micro-example Final state: low contains [3, 1]; high contains [5, 15]. The sorted stream is [1, 3, 5, 15], and the heap roots expose the middle pair without sorting.

Pitfalls

• The heap array's internal order is not a sorted list.
• A transfer during rebalancing changes both the partition and the roots.
• Always compute the median from the current state, not from an earlier snapshot.

Recap

• Four inserts require only local heap operations.
• Rebalancing after 3 is the decisive step.
• The final answer is 4, matching the sorted interpretation.

Learning goal: Diagnose the failure mode that makes a two-heap median incorrect.

Core idea Heap order alone is not enough. If one heap grows much larger than the other, its top may represent a value far from the true middle. The heaps must remain partitioned and balanced after every addNum() call, even if the next operation is another insertion rather than a query.

Algorithm plan

• Decide the destination using the current boundary, usually low.top.
• Repair a two-item size advantage by moving one root.
• Confirm that low.top <= high.top whenever both heaps are nonempty.
• Handle duplicates exactly like ordinary values.
• Use numeric division for even counts.

Micro-example Suppose values [1, 2, 100, 101] are incorrectly stored with three values in low and one in high. Returning low.top = 2 would be wrong; the true median is (2 + 100) / 2 = 51.

Pitfalls

• Moving the wrong root can violate the partition order.
• Assuming the larger heap is always high conflicts with the chosen size convention.
• Integer division can truncate an even-count median in some languages.

Recap

• Balance is correctness, not just optimization.
• Check both ordering and size invariants.
• Duplicates and negative values need no special algorithm.

Learning goal: Connect the heap operations to the target time and space bounds.

Core idea Each number is stored in exactly one heap, so the total space is linear. Insertion into a binary heap takes O(log n), and a rebalance moves at most one root, also taking O(log n). Reading heap tops is direct, so findMedian() takes O(1).

Algorithm plan

• Charge the destination insertion to O(log n).
• Charge a possible root transfer to another O(log n) operation.
• Treat median lookup as constant work because heap tops are already exposed.
• Store all n stream values across the two heaps.

Micro-example For 50,000 insertions, the structure never sorts all 50,000 values during a query. Each insertion adjusts a logarithmic-height heap, while each median request reads one or two roots.

Pitfalls

• Saying findMedian() is O(log n) overlooks that no heap mutation is needed.
• Calling the total space O(log n) ignores that every input remains stored.
• Amortized language is unnecessary here: each insertion has a logarithmic worst-case bound.

Recap

• addNum: O(log n) time.
• findMedian: O(1) time.
• Storage: O(n) space.
• The central invariant keeps the middle visible at all times.