How do you approach Find Median from Data Stream?

You could sort the list each time, but that is O(n log n) per findMedian.

What is the time complexity of Find Median from Data Stream?

Time complexity: O(log n) per addNum, O(1) per findMedian. Space complexity: O(n).

What are common mistakes on Find Median from Data Stream?

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k). An inverted comparator, which is silent: the code runs and returns confidently wrong answers. Re-heapifying inside the loop instead of once up front.

gitGood.dev

← Back to problems

Find Median from Data Stream

HardData Structures

Description

The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement a data structure that supports the following operations: - `addNum(num)` - adds an integer number from the data stream to the data structure. - `findMedian()` - returns the median of all elements so far. **Input format:** An array of commands where each command is either `["addNum", num]` or `["findMedian"]`. Return an array of results where `addNum` produces `null` and `findMedian` produces the current median.

Example 1

Input: operations = [["addNum",1],["addNum",2],["findMedian"],["addNum",3],["findMedian"]]

Output: [null,null,1.5,null,2]

Explanation: After adding 1 and 2, median is (1+2)/2 = 1.5. After adding 3, median is 2.

Constraints

- -10^5 <= num <= 10^5 - There will be at least one addNum before any findMedian call. - At most 5 * 10^4 calls total.

Find Median from Data Stream: approach, complexity and pitfalls

A hard heap / priority queue problem, graded against 6 test cases (3 of them hidden).

The pattern: Heap / Priority Queue

A priority queue for "top k" and streaming-median questions.

Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.

More Heap / Priority Queueproblems →

If you are stuck

Show the 3-step hint ladder

You could sort the list each time, but that is O(n log n) per findMedian.
Use two heaps: a max-heap for the lower half and a min-heap for the upper half.
Keep the heaps balanced so their sizes differ by at most 1.

The optimal approach

Show the approach: Two Heaps (or Sorted Insertion)

Use a max-heap for the lower half and a min-heap for the upper half. When adding a number, place it in the correct heap and rebalance so sizes differ by at most 1. The median is the top of the larger heap, or the average of both tops if equal size.

Time: O(log n) per addNum, O(1) per findMedian
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.