HardHeapDesignData StreamUpdated Sep 2026

295. Find Median from Data Stream

Asked at Google, Meta, Amazon, Microsoft and 6 more

Difficulty

Hard

Time

O(log n) for addNum, O(1) for fi

Space

O(n)

Pattern

Heap

Companies

10

Problem

Design a class called MedianFinder that keeps track of numbers arriving one at a time from a stream, and can report the median of everything seen so far at any moment.

The median is the middle value when all numbers are sorted. If the count is odd, it is the single middle element. If the count is even, there is no single middle, so take the average of the two middle values. For example, the median of [2,3,4] is 3, and the median of [2,3] is 2.5.

Implement two methods: addNum(num) stores a new integer, and findMedian() returns the median of all stored numbers as a double. findMedian() is only called when at least one number has been added. Answers within 10^-5 of the true value are accepted.

The median splits the data in half

sorted so fartwo middles1201Even count: median = (1 + 2) / 2 = 1.5sorted so far123012Odd count: the single middle value 2 is the median
Sort all numbers seen so far; the median is the middle one, or the average of the two middle ones when the count is even.

Constraints

  • ●-10^5 <= num <= 10^5
  • ●findMedian is called only when the structure holds at least one element
  • ●At most 5 * 10^4 total calls to addNum and findMedian

Examples

Example 1
Input["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]
Output[null, null, null, 1.5, null, 2.0]
WhyAfter adding 1 and 2 the sorted list is [1,2]. Two values means we average the two middle ones: (1+2)/2 = 1.5. After adding 3 the list is [1,2,3], an odd count, so the middle value 2 is the median.

Asked At

10 companies
CompanyDifficulty
GoogleHardView all Google questions →
MetaHardView all Meta questions →
AmazonHardView all Amazon questions →
MicrosoftHardView all Microsoft questions →
AppleHardView all Apple questions →
NetflixHardView all Netflix questions →
UberHardView all Uber questions →
AtlassianHardView all Atlassian questions →
TikTokHardView all TikTok questions →
DE ShawHardView all DE Shaw questions →

How to Think About It

1

Use two heaps: a max-heap for the lower half and a min-heap for the upper half.

2

Balance invariant: the max-heap can have at most one more element than the min-heap. This ensures the median is always at the top of one or both heaps.

3

On addNum: push to one heap, then rebalance. If the max of lower half > min of upper half, swap them.

4

Median: if sizes differ, return the max-heap top (extra element). Otherwise, average both tops.

5

Edge cases: single element (that element), even/odd count, negative numbers.

Optimal Approach

class MedianFinder:
lo = [] (max-heap, store negatives)
hi = [] (min-heap)

addNum(num):
push -num to lo
push -heappop(lo) to hi (move max of lo to hi)
if len(hi) > len(lo): push -heappop(hi) to lo (rebalance)

findMedian():
if len(lo) > len(hi): return -lo[0]
return (-lo[0] + hi[0]) / 2

Time: O(log n) add, O(1) find. Space: O(n).

Two heaps, one for each half

lo (max-heap)5← topaddNum(5): lo = [5], hi = [] — lo may hold one extralo (max-heap)5← topaddNum(15): push 15 to lo, then move lo's max (15) tohihi (min-heap)15← topnow lo = [5], hi = [15], sizes are equalpush num to lomove lo's max to hiif hi bigger, move hi's min back to lomedian = -lo[0] if odd, else (-lo[0] + hi[0]) / 2
lo holds the smaller half as a max-heap, hi holds the larger half as a min-heap; the median lives at the tops.
ComplexityTime O(log n) for addNum, O(1) for fiSpace O(n)Each addNum does a constant number of heap pushes and pops, each O(log n); findMedian only reads the two heap tops.

What Trips People Up in Real Interviews

1

Using a sorted list. Insert is O(n), not O(log n). Use two heaps for O(log n) insert.

2

Confusing "median" with "mean." The median is the middle value (odd count) or average of two middle values (even count).

3

Not maintaining the balance invariant. The max-heap can have at most one more element than the min-heap.

4

Forgetting to handle the case where heaps are equal size. The average of both tops is the median.

5

Pushing to the wrong heap first. Always push to lo (max-heap), then move the max of lo to hi (min-heap), then rebalance. Pushing to hi first can break the balance invariant.

Solution Code

O(log n) for addNum, O(1) for fi time
import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (inverted)
        self.hi = []  # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find Median from Data Stream problem?

Design a data structure that supports addNum(int num) and findMedian() in `O(log n)` and `O(1)` time respectively. This is a classic system design and algorithm hybrid question.

How do you solve Find Median from Data Stream?

The optimal approach runs in O(log n) for addNum, O(1) for fi time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find Median from Data Stream?

Find Median from Data Stream is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, TikTok, DE Shaw. It is a hard difficulty problem.

What are common mistakes on Find Median from Data Stream?
  • Using a sorted list. Insert is `O(n)`, not `O(log n)`. Use two heaps for `O(log n)` insert.
  • Confusing "median" with "mean." The median is the middle value (odd count) or average of two middle values (even count).
  • Not maintaining the balance invariant. The `max-heap` can have at most one more element than the `min-heap`.
  • Forgetting to handle the case where heaps are equal size. The average of both tops is the median.
  • Pushing to the wrong heap first. Always push to lo (`max-heap`), then move the max of lo to hi (`min-heap`), then rebalance. Pushing to hi first can break the balance invariant.