Blind 75 · Heap / Priority Queue

Find Median from Data Stream

Hard

Problem

Numbers arrive one at a time; after each arrival, report the median of everything seen so far.
Given the arrivals as an array nums, return an array of the same length where entry i is the median after nums[i] arrived — DOUBLED, so the answer stays integral when the median falls between two values: a median of 1.5 reports as 3.
The point of the problem is doing each step in O(log n); re-sorting per arrival is the answer to beat.

Examples

Example 1:
Input: nums = [1,2,3]
Output: [2,3,4]
Explanation: medians 1, 1.5, 2 — doubled: 2, 3, 4.

Example 2:
Input: nums = [5]
Output: [10]

Example 3:
Input: nums = [2,2,2,2]
Output: [4,4,4,4]

Example 4:
Input: nums = [6,10,2,6,5,0]
Output: [12,16,12,12,12,11]

Constraints

1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5

Prerequisites

Heaps — constant-time access to the smallest or largest, logarithmic insert and removal.

How to think about it

1. Two Heaps Facing Each Other Optimal

Intuition

Keep the smaller half under a max-heap and the larger half under a min-heap, balanced so their sizes never differ by more than one. Then the median is always at the tops: the bigger heap's top when the count is odd, both tops averaged when it is even — which is exactly the doubled median this version asks for. Re-sorting the data on every arrival is the O(n log n)-per-step answer this replaces.

Algorithm

1. Push the new number into the max-heap, then move its top into the min-heap.
2. If the min-heap is now larger, move its top back.
3. Report: twice the max-heap's top when sizes differ, otherwise the two tops summed.

Time & Space

Time O(log n) per arrival. Space O(n).