Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Design a data structure that receives integers one at a time and can report the median of everything seen so far. If the count is odd, the median is the single middle value after sorting. If the count is even, it is the average of the two middle values.

Sorting the entire stream after every insertion would make each query unnecessarily expensive. Keeping one sorted list is also costly because inserting near the front requires shifting many elements. The key observation is that a median query needs only the largest value in the lower half and the smallest value in the upper half—not the complete sorted order within either half.

Deriving the two-heap solution

Split all values into two groups:

  • A lower half whose largest value is immediately available.
  • An upper half whose smallest value is immediately available.

A max-heap is ideal for the lower half, while a min-heap is ideal for the upper half. Python only provides a min-heap, so the lower-half values are stored negated. Its smallest stored value is therefore the negative of the largest real value in that half.

The data structure maintains two invariants:

  1. Every value in the lower half is less than or equal to every value in the upper half.
  2. The lower half has either the same number of values as the upper half or exactly one more.

To add a number, compare it with the largest value in the lower half and place it in the appropriate heap. Then move one heap root if the sizes have drifted out of balance. Moving only roots preserves the ordering invariant because those roots are precisely the values nearest the boundary between the halves.

Once the invariants hold, the median is immediate. For an odd count, the lower heap has one extra value, so its root is the median. For an even count, the two heap roots are the middle pair and their average is the median.

Each insertion performs a constant number of heap operations and takes O(log n) time. A median query takes O(1) time, and storing all values takes O(n) space.

Python solution

import heapq
from typing import List


class MedianFinder:
    """Maintain the median of an incrementally received sequence of integers."""

    def __init__(self) -> None:
        # Python has no max-heap, so lower-half values are stored negated.
        self._lower_half: List[int] = []
        self._upper_half: List[int] = []

    def addNum(self, number: int) -> None:
        """Add one value while preserving the heap ordering and size invariants."""
        if not self._lower_half or number <= -self._lower_half[0]:
            heapq.heappush(self._lower_half, -number)
        else:
            heapq.heappush(self._upper_half, number)

        self._rebalance()

    def findMedian(self) -> float:
        """Return the current median in constant time.

        LeetCode guarantees that this method is called after an insertion. The
        explicit check makes the class safer when used outside that contract.
        """
        if not self._lower_half:
            raise ValueError("The median is undefined for an empty data stream")

        if len(self._lower_half) > len(self._upper_half):
            return float(-self._lower_half[0])

        lower_middle = -self._lower_half[0]
        upper_middle = self._upper_half[0]
        return (lower_middle + upper_middle) / 2.0

    def _rebalance(self) -> None:
        """Keep the lower heap equal in size to, or one larger than, the upper."""
        if len(self._lower_half) > len(self._upper_half) + 1:
            largest_lower = -heapq.heappop(self._lower_half)
            heapq.heappush(self._upper_half, largest_lower)
        elif len(self._upper_half) > len(self._lower_half):
            smallest_upper = heapq.heappop(self._upper_half)
            heapq.heappush(self._lower_half, -smallest_upper)

Interview follow-ups

Can insertion and median lookup both be O(log n) with a balanced search tree?

Yes. A self-balancing binary search tree augmented with subtree sizes can insert a value and select the value at a given rank in O(log n) time. It also supports operations that heaps do not handle naturally, such as deleting an arbitrary value or asking for any percentile. The tradeoff is that median lookup becomes O(log n) instead of O(1), and Python’s standard library does not provide an order-statistics tree, so the implementation is substantially more complex.

What if every number is known to be between 0 and 100?

Keep an array of 101 frequencies plus the total number of values. Insertion increments one counter in O(1) time. To answer a median query, scan the counters until reaching the middle rank or ranks; because the domain size is fixed at 101, this is effectively O(1) time and uses O(1) space. This works because the bounded domain replaces the need to store and order individual values.

What if 99 percent of the numbers are between 0 and 100?

Use the same frequency array for the common range and track out-of-range values separately, for example in two ordered structures or heaps for values below 0 and above 100. The counts in those side structures reveal whether a median rank lies outside the main range. The usual case remains fast and compact, but the implementation must still retain every outlier that could become relevant; worst-case space remains O(n) if the distribution stops matching the assumption.

How would the design support deleting old values from a sliding window?

Two heaps can still work, but a heap cannot efficiently remove an arbitrary buried element. Add a hash map of pending deletion counts and discard marked values lazily whenever they reach a heap root. Maintain logical heap sizes separately from their physical lengths so rebalancing ignores stale entries. Insertions and deletions are amortized O(log k) for a window of size k, median lookup is O(1) after pruning, and the bookkeeping is more delicate than in the insertion-only version.

How can the structure return an arbitrary percentile instead of only the median?

The two-heap size rule is specialized to a 50th-percentile boundary. For a fixed percentile, rebalance the heaps so the lower heap contains the required number of smallest elements, and read its root as the boundary value. If callers may request many different percentiles, an order-statistics tree is a better fit because it can select any rank in O(log n) time without repartitioning the data for every query.

How would this work when the stream is distributed across many machines?

Exact medians are difficult to merge from only per-machine medians because those summaries discard too much ordering information. Workers could send mergeable ordered counts when the value domain is small, or retain data in mergeable sorted runs for an exact but more expensive selection step. At large scale, a mergeable quantile sketch is often preferred: it uses bounded memory and network traffic and combines cleanly across workers, but it returns an approximate median with a stated error guarantee rather than the exact value.