• -10⁵ <= num <= 10⁵
• At most 5 × 10⁴ calls in total to addNum and findMedian.
• findMedian is never called before the first addNum.
• Numbers arrive one at a time and cannot be re-read in bulk.
• Follow-up: how would you optimise if every number were in the range [0, 100]?

The word doing the damage is stream. If all the numbers were handed to you at once, this would be a one-line problem: sort, read the middle. Instead they arrive one at a time and the answer may be demanded after any of them. So the real question is not "how do I find a median" but "what can I maintain as numbers arrive, so that the middle is always instantly available?"

The first attempt keeps everything in a list and sorts on demand.

def add_num(self, num):
    self.data.append(num)               # O(1)

def find_median(self):
    self.data.sort()                    # O(N log N) every single query
    n = len(self.data)
    mid = n // 2
    if n % 2 == 1:
        return float(self.data[mid])
    return (self.data[mid - 1] + self.data[mid]) / 2.0

Adding is instant, but every query re-sorts from scratch. Under alternating calls with 5 × 10⁴ numbers, that is tens of thousands of sorts over lists tens of thousands long — billions of operations for an answer that barely moves between calls. The waste is glaring: the list was already sorted a moment ago, and one new number cannot un-sort it.

That thought leads to attempt two. Keep the list sorted at all times, and slot each newcomer into its proper place. Binary search finds the correct index in O(log N) — but inserting there means physically shifting every later element one position right, which is O(N).

import bisect

def add_num(self, num):
    bisect.insort(self.data, num)       # O(log N) to locate, O(N) to shift

def find_median(self):
    n = len(self.data)
    mid = n // 2
    if n % 2 == 1:
        return float(self.data[mid])
    return (self.data[mid - 1] + self.data[mid]) / 2.0

Queries are now free, and the total cost drops a lot in practice — memory moves are fast. But asymptotically we are still linear per operation, and the reason is instructive: we are paying to maintain a total order over all N numbers when the query only ever reads the one or two elements in the middle. The ranking of the 400th smallest against the 401st is computed, stored, and never used.

Stop thinking about a sorted list and think about a split point. Cut the numbers into two piles of equal size, where every number in the left pile is less than or equal to every number in the right pile. The piles are unordered internally — they are just sets — and yet the median is fully determined by them: if the piles are equal in size, it is the average of the largest number on the left and the smallest on the right; if the left pile holds one extra, it is that largest-on-the-left.

That is the entire insight. The median depends only on the two values sitting at the border. Everything deep inside either pile is irrelevant to the answer and does not need to be ordered at all.

Now the mechanical question, the same one asked in Kth Largest: which structure gives instant access to the extreme of a pile? The left pile needs its maximum on tap, so it is a max-heap. The right pile needs its minimum on tap, so it is a min-heap. Two heaps, facing each other across the border, with the median wedged between their roots.

Two properties must hold after every single addition, and the code exists only to restore them:

A new number could belong on either side, and checking which requires a comparison and then possibly a fix-up — easy to get wrong at boundaries. There is a two-step trick that handles every case without any comparison at all:

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []     # left pile, max-heap via negated values
        self.large = []     # right pile, min-heap

    def add_num(self, num):
        # Step 1: everything enters on the left.
        heapq.heappush(self.small, -num)
        # Step 2: hand the left's largest over to the right.
        #         This is what guarantees order: whatever ends up
        #         on the left is no bigger than anything on the right.
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # Step 3: if the right outgrew the left, hand its smallest back.
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return float(-self.small[0])                  # odd: the extra sits left
        return (-self.small[0] + self.large[0]) / 2.0     # even: average the border

Note that small stores negated values because Python provides only a min-heap; negating flips the comparison so the largest original value has the smallest stored key and sits at the root. Every read of it negates back.

Each addition performs a constant number of heap operations, so addNum is O(log N) and findMedian is O(1) — it only peeks at two roots. Memory is O(N), which is unavoidable since any exact median needs the data.

Adding 6, 1, 5, then 4, querying along the way. The left pile is written as real values, not their negated storage.

At no point was anything sorted, and at no point did more than the two border values matter.

The follow-up asks what changes if every number lies in [0, 100]. This is the same escape hatch that appeared in Top K Frequent: when the key range is small and integral, stop comparing and start counting. Keep an array of 101 tallies plus a running total; addNum becomes a single increment, O(1). To find the median, walk the 101 buckets accumulating counts until you pass the halfway mark — a fixed 101 steps regardless of how many billions of numbers have streamed through. The log vanishes because the value range, not the data size, bounds the work.

The reflex to train is broader than heaps. When a problem asks for a value maintained over a stream, ask what is the least I can maintain that still determines the answer? For the median it is a border between two sets. For a running maximum it is one number. For a sliding-window maximum it is a monotonic deque. Each time, the win comes from noticing that the full sorted order was never the thing being asked for — and refusing to pay for it.