What happens if you sorting the entire list on every insertion?

Time limit exceeded on large inputs Fix: Use two heaps to maintain order efficiently

What happens if you not balancing the two heaps after insertion?

Median calculation becomes incorrect or throws errors Fix: Always ensure heaps sizes differ by at most one after each insertion

What happens if you using min heap for both halves or max heap for both halves?

Cannot correctly find median as ordering is lost Fix: Use max heap for lower half and min heap for upper half

What happens if you forgetting to negate values when simulating max heap in python?

Heap behaves as min heap, breaking logic Fix: Negate values when pushing and popping from max heap

Interview Prepchallenge-problemshardAmazonFacebookGoogleMicrosoft

Find Median from Data Stream

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Find Median from Data Stream

hardMIXEDAmazonFacebookGoogle

Imagine you are monitoring live sensor data or stock prices and need to report the median value at any moment as new data arrives continuously.

💡 This problem involves maintaining a dynamic data structure that can efficiently provide the median after each insertion. Beginners often struggle because the median depends on the order of elements, and naive methods require sorting after every insertion, which is inefficient.

📋

Problem Statement

Design a data structure that supports adding numbers from a data stream and finding the median of all elements so far. Implement two methods: addNum(int num) - adds a number to the data structure; findMedian() - returns the median of all elements added so far. The median is the middle value in an ordered integer list. If the size of the list is even, the median is the average of the two middle numbers.

1 ≤ number of addNum calls ≤ 10^5-10^5 ≤ num ≤ 10^5At least one element will be present before calling findMedian

💡

Example

Input"addNum(1), addNum(2), findMedian(), addNum(3), findMedian()"

Output1.5, 2

After adding 1 and 2, the sorted list is [1,2], median is (1+2)/2=1.5. After adding 3, list is [1,2,3], median is 2.

Only one element added → median is that element
All elements are the same → median is that element
Large number of elements with duplicates → median calculation remains correct
Alternating large and small numbers → median updates correctly

⚠️

Common Mistakes

Sorting the entire list on every insertion

Time limit exceeded on large inputs

✅ Use two heaps to maintain order efficiently

Not balancing the two heaps after insertion

Median calculation becomes incorrect or throws errors

✅ Always ensure heaps sizes differ by at most one after each insertion

Using min heap for both halves or max heap for both halves

Cannot correctly find median as ordering is lost

✅ Use max heap for lower half and min heap for upper half

Forgetting to negate values when simulating max heap in Python

Heap behaves as min heap, breaking logic

✅ Negate values when pushing and popping from max heap

Incorrect median calculation when total elements are even

Returns wrong median value

✅ Return average of two middle elements (tops of both heaps)

🧠

Brute Force (Sort on Every Insertion)

💡 This approach is the most straightforward and helps understand the problem by directly maintaining the entire data stream and sorting it each time we want the median. It is inefficient but conceptually simple.

Intuition

Store all numbers in a list. Each time a new number arrives, insert it and sort the list. The median is then the middle element(s) of the sorted list.

Algorithm

Initialize an empty list to store numbers.
For each new number, append it to the list.
Sort the list.
Return the middle element if odd length, or average of two middle elements if even.

💡 The main challenge is realizing that sorting after every insertion is costly, but this method guarantees correctness and clarifies the median concept.

</>

Code

class MedianFinder:
    def __init__(self):
        self.nums = []

    def addNum(self, num: int) -> None:
        self.nums.append(num)
        self.nums.sort()

    def findMedian(self) -> float:
        n = len(self.nums)
        mid = n // 2
        if n % 2 == 1:
            return float(self.nums[mid])
        else:
            return (self.nums[mid - 1] + self.nums[mid]) / 2

# Example usage:
# mf = MedianFinder()
# mf.addNum(1)
# mf.addNum(2)
# print(mf.findMedian())  # Output: 1.5
# mf.addNum(3)
# print(mf.findMedian())  # Output: 2.0

Line Notes

self.nums = []Initialize storage for all numbers received so far.

self.nums.append(num)Add the new number to the list before sorting.

self.nums.sort()Sort the entire list to maintain order for median calculation.

n = len(self.nums)Calculate current number of elements to find median position.

if n % 2 == 1:Check if the count is odd to return the middle element directly.

return float(self.nums[mid])Return the middle element as median for odd count.

return (self.nums[mid - 1] + self.nums[mid]) / 2Return average of two middle elements for even count.

import java.util.*;

class MedianFinder {
    private List<Integer> nums;

    public MedianFinder() {
        nums = new ArrayList<>();
    }

    public void addNum(int num) {
        nums.add(num);
        Collections.sort(nums);
    }

    public double findMedian() {
        int n = nums.size();
        int mid = n / 2;
        if (n % 2 == 1) {
            return (double) nums.get(mid);
        } else {
            return (nums.get(mid - 1) + nums.get(mid)) / 2.0;
        }
    }

    // Example usage:
    // public static void main(String[] args) {
    //     MedianFinder mf = new MedianFinder();
    //     mf.addNum(1);
    //     mf.addNum(2);
    //     System.out.println(mf.findMedian()); // 1.5
    //     mf.addNum(3);
    //     System.out.println(mf.findMedian()); // 2.0
    // }
}

Line Notes

nums = new ArrayList<>()Initialize dynamic array to store numbers.

nums.add(num)Add new number to the list before sorting.

Collections.sort(nums)Sort the list to maintain order for median calculation.

int n = nums.size()Get current number of elements to find median position.

if (n % 2 == 1)Check if the count is odd to return middle element.

return (double) nums.get(mid)Return middle element as median for odd count.

return (nums.get(mid - 1) + nums.get(mid)) / 2.0Return average of two middle elements for even count.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MedianFinder {
private:
    vector<int> nums;
public:
    MedianFinder() {}

    void addNum(int num) {
        nums.push_back(num);
        sort(nums.begin(), nums.end());
    }

    double findMedian() {
        int n = nums.size();
        int mid = n / 2;
        if (n % 2 == 1) {
            return (double)nums[mid];
        } else {
            return (nums[mid - 1] + nums[mid]) / 2.0;
        }
    }
};

// Example usage:
// int main() {
//     MedianFinder mf;
//     mf.addNum(1);
//     mf.addNum(2);
//     cout << mf.findMedian() << endl; // 1.5
//     mf.addNum(3);
//     cout << mf.findMedian() << endl; // 2.0
//     return 0;
// }

Line Notes

vector<int> nums;Store all numbers received so far in a dynamic array.

nums.push_back(num);Add new number to the vector before sorting.

sort(nums.begin(), nums.end());Sort the vector to maintain order for median calculation.

int n = nums.size();Get current number of elements to find median position.

if (n % 2 == 1)Check if the count is odd to return middle element.

return (double)nums[mid];Return middle element as median for odd count.

return (nums[mid - 1] + nums[mid]) / 2.0;Return average of two middle elements for even count.

class MedianFinder {
    constructor() {
        this.nums = [];
    }

    addNum(num) {
        this.nums.push(num);
        this.nums.sort((a, b) => a - b);
    }

    findMedian() {
        const n = this.nums.length;
        const mid = Math.floor(n / 2);
        if (n % 2 === 1) {
            return this.nums[mid];
        } else {
            return (this.nums[mid - 1] + this.nums[mid]) / 2;
        }
    }
}

// Example usage:
// const mf = new MedianFinder();
// mf.addNum(1);
// mf.addNum(2);
// console.log(mf.findMedian()); // 1.5
// mf.addNum(3);
// console.log(mf.findMedian()); // 2.0

Line Notes

this.nums = []Initialize array to store all numbers.

this.nums.push(num)Add new number to the array before sorting.

this.nums.sort((a, b) => a - b)Sort array numerically to maintain order for median.

const n = this.nums.lengthGet current number of elements to find median position.

if (n % 2 === 1)Check if count is odd to return middle element.

return this.nums[mid]Return middle element as median for odd count.

return (this.nums[mid - 1] + this.nums[mid]) / 2Return average of two middle elements for even count.

⏱

Complexity

TimeO(n log n) per addNum call due to sorting

SpaceO(n) to store all numbers

Each insertion requires sorting the entire list, which takes O(n log n). For n insertions, total time is O(n^2 log n).

💡 For n=1000, this means sorting 1000 elements 1000 times, which is about 1 million operations, too slow for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large data streams but is useful to understand the problem and median concept before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n log n) per insertion`	`O(n)`	No	N/A	Mention only - never code due to inefficiency
2. Balanced Two Heaps	`O(log n) per insertion, O(1) median retrieval`	`O(n)`	No	N/A	Code this approach for optimal solution
3. Balanced Two Heaps with Lazy Removal	`O(log n) per insertion/removal, O(1) median retrieval`	`O(n)`	No	N/A	Mention if asked about removals or sliding window median

Practice

(1/5)

1. Consider the following Python code implementing the optimal CustomStack with lazy increments. After executing the sequence of operations below, what is the output of the last pop() call?

cs = CustomStack(3)
cs.push(1)
cs.push(2)
cs.increment(2, 5)
print(cs.pop())

easy

A. 2

B. 7

C. 6

D. 1

3. The following code attempts to implement the optimal CustomStack with lazy increments. Identify the line containing the subtle bug that causes incorrect increment propagation.

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.inc = [0] * maxSize
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        self.stack.append(x)  # Line 8

    def pop(self) -> int:
        if not self.stack:
            return -1
        i = len(self.stack) - 1
        if i > 0:
            self.inc[i-1] += self.inc[i]
        res = self.stack.pop() + self.inc[i]
        self.inc[i] = 0
        return res

    def increment(self, k: int, val: int) -> None:
        limit = min(k, len(self.stack))
        if limit > 0:
            self.inc[limit-1] += val

medium

A. Line 8: push appends without checking maxSize

B. Line 13: returning -1 when stack is empty

C. Line 16: incrementing inc[i-1] by inc[i] during pop

D. Line 20: increment method updates inc array at limit-1

5. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace the increment operation

Step 2: Trace the pop operation

Final Answer:

Quick Check:

Solution

Step 1: Understand the operations required

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Check push method

Step 2: Verify other lines

Final Answer:

Quick Check:

Solution

Step 1: Analyze data structures used

Step 2: Consider operations in put

Final Answer:

Quick Check:

Solution

Step 1: Analyze set() method

Step 2: Consequence on get()

Final Answer:

Quick Check: