LeetCode 295 · Heap / Priority Queue

Find Median from Data Stream, explained with a picture

Two waiting rooms with the median at the door.

HardHeap / Priority Queue
▶ Watch it step by step

The problem

Design a structure that receives numbers one by one and can return the median of all numbers so far at any time.

Input:  add 5, 15, 1, 3, 8, 7 (asking for the median after each)
Output: 5, 10, 5, 4, 5, 6

Picture it

Picture two waiting rooms. The left room holds the smaller half of people (tallest at the door, a max-heap), the right room the taller half (shortest at the door, a min-heap). We keep the rooms the same size (left may have one extra). The median is the person at the left door, or the average of the two people at the doors.

How to recognise it

  • Numbers arrive one at a time, and at any moment you may be asked for the median (the middle value, or the average of the two middle values for an even count).
  • Queries and insertions are mixed, so you cannot sort once and be done.
  • The median needs the boundary between the smaller half and the larger half, not the full order.
  • Up to 5 × 10^4 calls rule out a re-sort per query.
  • "Track the middle of a changing collection" points to two heaps (trees stored in lists with O(log n) push and pop): a max-heap for the lower half and a min-heap for the upper half.

Start with brute force

Keep every number in a list. When the median is asked for, sort the list and read the middle.

class MedianFinderBrute:
    def __init__(self):
        self.nums = []

    def add_num(self, x):
        self.nums.append(x)

    def find_median(self):
        s = sorted(self.nums)
        n = len(s)
        if n % 2:
            return s[n // 2]
        return (s[n // 2 - 1] + s[n // 2]) / 2

Adding is O(1), but each query sorts up to n numbers: O(n log n). With 5 × 10^4 numbers, a sort is about 8 × 10^5 steps, and 2.5 × 10^4 queries make roughly 2 × 10^10 steps. Space is O(n).

From brute force to the idea

  1. Find the waste. To read the median you only need the largest of the lower half and the smallest of the upper half, yet the sort orders everything on every query.
  2. Split into two halves. Keep the smaller half in a max-heap low (stored negated, because heapq is a min-heap) and the larger half in a min-heap high. Every number in low is at most every number in high.
  3. Keep the sizes balanced. low has the same count as high, or one more.
  4. Insert in a way that keeps both rules. Push x into low, then move low's largest into high. This guarantees the largest of the lower half is not bigger than anything in high. If high is now longer, move its smallest back into low.
  5. Read the median at the doors. Odd count: the front of low. Even count: the average of the two fronts.

This is the key idea: two heaps meeting at the median, with O(log n) inserts and O(1) reads.

The key idea

Two heaps split the data into halves; rebalance after each insert. Add O(log n), median O(1).

Python solution

class MedianFinder:
    def __init__(self):
        self.low, self.high = [], []    # max-heap (negated), min-heap
    def add_num(self, x):
        heappush(self.low, -x)
        heappush(self.high, -heappop(self.low))
        if len(self.high) > len(self.low):
            heappush(self.low, -heappop(self.high))
    def find_median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceadd_num O(1); find_median O(n log n)O(n)
Two heaps (shown code)add_num O(log n): three heap operations at most; find_median O(1)O(n): every number lives in one of the heaps

Edge cases

  • One number: low has it; the median is that number.
  • Two numbers: the average of both, as a float: 5 and 7 give 6.0.
  • Output types: an odd count returns the stored int (5), an even count returns a float (10.0), because of / 2. The problem accepts answers within 10^-5.
  • Duplicates (5, 5, 5, 5): medians are 5, 5.0, 5, 5.0.
  • Negative numbers: work, because only the sign of the stored values is flipped.
  • Example (5, 15, 1, 3, 8, 7): the medians are 5, 10.0, 5, 4.0, 5, 6.0.
  • No numbers yet: find_median raises IndexError. The problem promises at least one number before each query.
  • Imports: the snippet needs from heapq import heappush, heappop.

Common mistakes

  • Pushing straight into one heap and balancing only by size. Counts look fine but the halves overlap: adding 1, 2, 3 then gives 3 as the median instead of 2.
  • Forgetting to negate when pushing to or reading from low.
  • Using // for the average and losing the .5.
  • Re-sorting a list inside add_num, which makes the insert O(n log n).
Your turn: numbers from 0 to 100 only

Every number is an integer from 0 to 100. Support the same two operations without heaps. Describe your approach, then write it if you like.

Compare with our answer

With only 101 possible values, count how often each appears. To find the median, walk the counts from 0 upward until the running total reaches the middle rank.

class MedianFinderSmall:
    def __init__(self):
        self.counts = [0] * 101
        self.n = 0

    def add_num(self, x):
        self.counts[x] += 1
        self.n += 1

    def _kth(self, r):                  # r-th smallest, counting from 1
        for value, c in enumerate(self.counts):
            r -= c
            if r <= 0:
                return value

    def find_median(self):
        lo = self._kth((self.n + 1) // 2)
        hi = self._kth(self.n // 2 + 1)
        return (lo + hi) / 2

Adding is O(1) and a query is O(101), which is O(1) in n. Space is O(101).

A strong answer mentions: a counting array indexed by value, finding the middle rank(s) by a cumulative scan, and that this beats heaps only because the value range is tiny.

Check what stuck

1. A monitoring system receives one latency reading per second and must show the current median at any time. Which structure fits best?

2. Why does the shown add_num push x into low and then move one item to high, instead of choosing a heap by comparing x with the fronts?

3. A learner replaces the body of add_num with heappush(self.low, -x) followed by if len(self.low) > len(self.high) + 1: heappush(self.high, -heappop(self.low)). Which sequence exposes the bug?

Score 60% or more and the lesson is marked complete.