LeetCode 295 Find Median from Data Stream - Example and Complexity Analysis

Trace adding 1, 5, 2.

Add 1: maxHeap = [1], minHeap = []. Median = 1.

Add 5: Add to max, push to min. maxHeap = [], minHeap = [5]. Rebalance: minHeap larger, move 5 back. Wait, let's trace properly:

• Push 5 to maxHeap: [5, 1] (max at top is 5).
• Pop max (5), push to minHeap: maxHeap = [1], minHeap = [5].
• Sizes equal. Median = (1 + 5) / 2 = 3.

Add 2:

• Push to maxHeap: [2, 1].
• Pop max (2), push to minHeap: maxHeap = [1], minHeap = [2, 5].
• minHeap larger, pop min (2), push to maxHeap: maxHeap = [2, 1], minHeap = [5].
• Median = 2 (maxHeap top).

$O(\log n)$ per add (heap operations). $O(1)$ for findMedian. $O(n)$ space.