Find Median from Data Stream

Problem

The median is the middle value in an ordered integer list. Implement the MedianFinder class that supports addNum and findMedian operations.

Examples

The brute-force approach

Keep a sorted list. On each addNum, insert in sorted position (O(n) shift). On findMedian, return the middle element.

def addNum(num):
    # binary search for position, then insert
    bisect.insort(data, num)

def findMedian():
    n = len(data)
    if n % 2 == 1: return data[n//2]
    return (data[n//2 - 1] + data[n//2]) / 2

Insertion into a sorted list costs O(n) due to the array shift. For n total numbers, total cost is O(n²).

Spotting the pattern

This is a Two Heaps problem. The key question to ask yourself:

If you could instantly see both the largest number in the bottom half and the smallest number in the top half, what would the median be?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.