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

🎯

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 buggy code snippet for the IPO problem. Which line contains the subtle bug that causes incorrect results or inefficiency?

medium

A. Line pushing projects into min_capital_heap without sorting

B. Line popping from min_capital_heap in the while loop

C. Line pushing profits into max_profit_heap with negation

D. Line breaking the loop when max_profit_heap is empty

2. Consider the following buggy code snippet for the two heaps approach to find next intervals. Which line contains the subtle bug that causes incorrect results on some inputs?

import heapq

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n
    max_start_heap = []
    max_end_heap = []

    for i, (start, end) in enumerate(intervals):
        heapq.heappush(max_start_heap, (start, i))  # Line 9
        heapq.heappush(max_end_heap, (-end, i))

    while max_end_heap:
        end, end_idx = heapq.heappop(max_end_heap)
        end = -end

        if not max_start_heap or -max_start_heap[0][0] < end:
            continue

        candidates = []
        while max_start_heap and -max_start_heap[0][0] >= end:
            start, start_idx = heapq.heappop(max_start_heap)
            candidates.append((start, start_idx))

        min_start, min_idx = max(candidates)
        result[end_idx] = min_idx

        for c in candidates:
            if c != (min_start, min_idx):
                heapq.heappush(max_start_heap, c)

    return result

medium

A. Line 12: Pushing intervals into max_end_heap with negative end times.

B. Line 9: Using a min-heap push with (start, i) instead of max-heap with (-start, i).

C. Line 18: Checking if max_start_heap is empty or top start < end incorrectly.

D. Line 26: Pushing back unused candidates into max_start_heap.

4. Identify the bug in the following code snippet for the optimized task scheduler:

def task_scheduler_buggy(tasks, space):
    next_available = {}
    day = 1
    for t in tasks:
        if t in next_available:
            day = next_available[t]  # Bug here
        next_available[t] = day + space + 1
        day += 1
    return day - 1

medium

A. Line 6: Using assignment instead of max to update day causes cooldown violation

B. Line 4: Missing initialization of next_available dictionary

C. Line 7: Incorrect calculation of next_available day for task

D. Line 8: Incrementing day after scheduling causes off-by-one error

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

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: Identify heap initialization

Step 2: Understand impact

Final Answer:

Quick Check:

Solution

Step 1: Identify heap usage

Step 2: Analyze Line 9

Final Answer:

Quick Check:

Solution

Step 1: Identify operations per element

Step 2: Calculate total complexity

Final Answer:

Quick Check:

Solution

Step 1: Analyze day update logic

Step 2: Correct approach

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse implication

Step 2: Modify algorithm accordingly

Final Answer:

Quick Check:

Ready to prove it?