Find Median from Data Stream

🎯

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

1. Initialize an empty list to store numbers.
2. For each new number, append it to the list.
3. Sort the list.
4. 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.

🧠

Balanced Two Heaps (Max-Heap and Min-Heap)

💡 This approach uses two heaps to maintain the lower and upper halves of the data stream, allowing efficient median retrieval without sorting the entire list each time.

Intuition

Use a max-heap to store the smaller half of numbers and a min-heap for the larger half. Balance their sizes so that the median is either the top of one heap or the average of the tops of both.

Algorithm

1. Initialize two heaps: max-heap for lower half, min-heap for upper half.
2. For each new number, add it to one of the heaps based on comparison with max-heap top.
3. Balance the heaps so their sizes differ by at most one.
4. Calculate median from the tops of the heaps depending on their sizes.

💡 The key is maintaining balance and ordering between the two heaps to quickly find the median without sorting all elements.

</>

Code

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (invert values)
        self.large = []  # min heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        if self.small and self.large and (-self.small[0]) > self.large[0]:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        else:
            return (-self.small[0] + self.large[0]) / 2

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

Line Notes

self.small = [] # max heap (invert values)Use a min heap with negated values to simulate max heap for lower half.

self.large = [] # min heapMin heap stores the larger half of numbers.

heapq.heappush(self.small, -num)Add new number to max heap by negating it.

if self.small and self.large and (-self.small[0]) > self.large[0]Ensure max heap top is not greater than min heap top to maintain order.

val = -heapq.heappop(self.small)Pop from max heap to balance.

heapq.heappush(self.large, val)Push to min heap to balance.

if len(self.small) > len(self.large) + 1Balance heaps if max heap is too large.

elif len(self.large) > len(self.small)Balance heaps if min heap is larger.

val = heapq.heappop(self.large)Pop from min heap.

heapq.heappush(self.small, -val)Push to max heap after negation.

if len(self.small) > len(self.large)If max heap has more elements, median is its top.

return float(-self.small[0])Return median from max heap top.

return (-self.small[0] + self.large[0]) / 2Return average of tops if heaps equal size.

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> small; // max heap
    private PriorityQueue<Integer> large; // min heap

    public MedianFinder() {
        small = new PriorityQueue<>(Collections.reverseOrder());
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // Add to min heap first
        if (large.isEmpty() || num >= large.peek()) {
            large.offer(num);
        } else {
            small.offer(num);
        }

        // Balance the heaps sizes
        if (large.size() > small.size() + 1) {
            small.offer(large.poll());
        } else if (small.size() > large.size()) {
            large.offer(small.poll());
        }
    }

    public double findMedian() {
        if (large.size() > small.size()) {
            return (double) large.peek();
        } else {
            return (large.peek() + small.peek()) / 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

small = new PriorityQueue<>(Collections.reverseOrder())Max heap implemented by reversing natural order.

large = new PriorityQueue<>()Min heap for larger half of numbers.

// Add to min heap firstAdd new number to min heap if it belongs to larger half.

if (large.isEmpty() || num >= large.peek())Check if number belongs to larger half.

large.offer(num)Add to min heap.

elseOtherwise, add to max heap for smaller half.

small.offer(num)Add to max heap.

// Balance the heaps sizesEnsure heaps sizes differ by at most one.

if (large.size() > small.size() + 1)If min heap too large, move element to max heap.

small.offer(large.poll())Move element from min heap to max heap.

else if (small.size() > large.size())If max heap too large, move element to min heap.

large.offer(small.poll())Move element from max heap to min heap.

if (large.size() > small.size())If min heap has more elements, median is its top.

return (double) large.peek()Return median from min heap top.

return (large.peek() + small.peek()) / 2.0Return average of tops if heaps equal size.

#include <iostream>
#include <queue>

using namespace std;

class MedianFinder {
private:
    priority_queue<int> small; // max heap
    priority_queue<int, vector<int>, greater<int>> large; // min heap
public:
    MedianFinder() {}

    void addNum(int num) {
        if (large.empty() || num >= large.top()) {
            large.push(num);
        } else {
            small.push(num);
        }

        if (large.size() > small.size() + 1) {
            small.push(large.top()); large.pop();
        } else if (small.size() > large.size()) {
            large.push(small.top()); small.pop();
        }
    }

    double findMedian() {
        if (large.size() > small.size()) {
            return (double)large.top();
        } else {
            return (large.top() + small.top()) / 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

priority_queue<int> small;Max heap stores smaller half of numbers.

priority_queue<int, vector<int>, greater<int>> large;Min heap stores larger half of numbers.

if (large.empty() || num >= large.top())Add new number to min heap if it belongs to larger half.

large.push(num);Add to min heap.

elseOtherwise, add to max heap for smaller half.

small.push(num);Add to max heap.

if (large.size() > small.size() + 1)Balance heaps if min heap too large.

small.push(large.top()); large.pop();Move element from min heap to max heap.

else if (small.size() > large.size())Balance heaps if max heap too large.

large.push(small.top()); small.pop();Move element from max heap to min heap.

if (large.size() > small.size())If min heap has more elements, median is its top.

return (double)large.top();Return median from min heap top.

return (large.top() + small.top()) / 2.0;Return average of tops if heaps equal size.

class MedianFinder {
    constructor() {
        this.small = new MaxHeap(); // max heap
        this.large = new MinHeap(); // min heap
    }

    addNum(num) {
        if (this.large.isEmpty() || num >= this.large.peek()) {
            this.large.insert(num);
        } else {
            this.small.insert(num);
        }

        if (this.large.size() > this.small.size() + 1) {
            this.small.insert(this.large.extractMin());
        } else if (this.small.size() > this.large.size()) {
            this.large.insert(this.small.extractMax());
        }
    }

    findMedian() {
        if (this.large.size() > this.small.size()) {
            return this.large.peek();
        } else {
            return (this.large.peek() + this.small.peek()) / 2;
        }
    }
}

// Note: MaxHeap and MinHeap classes must be implemented with insert, extractMax/extractMin, peek, size, and isEmpty methods.

// 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.small = new MaxHeap()Max heap stores smaller half of numbers.

this.large = new MinHeap()Min heap stores larger half of numbers.

if (this.large.isEmpty() || num >= this.large.peek())Add new number to min heap if it belongs to larger half.

this.large.insert(num)Insert into min heap.

elseOtherwise, add to max heap for smaller half.

this.small.insert(num)Insert into max heap.

if (this.large.size() > this.small.size() + 1)Balance heaps if min heap too large.

this.small.insert(this.large.extractMin())Move element from min heap to max heap.

else if (this.small.size() > this.large.size())Balance heaps if max heap too large.

this.large.insert(this.small.extractMax())Move element from max heap to min heap.

if (this.large.size() > this.small.size())If min heap has more elements, median is its top.

return this.large.peek()Return median from min heap top.

return (this.large.peek() + this.small.peek()) / 2Return average of tops if heaps equal size.

⏱

Complexity

TimeO(log n) per addNum call, O(1) per findMedian call

SpaceO(n) to store all numbers in heaps

Each insertion involves heap operations which take O(log n). Median retrieval is constant time by peeking heap tops.

💡 For n=100000, this means about 100000 * log2(100000) ≈ 1.6 million operations, which is efficient enough for real-time data streams.

Interview Verdict: Accepted / Optimal for large data streams

This approach balances efficiency and correctness, making it the preferred solution in interviews.

🧠

Balanced Two Heaps with Lazy Removal (for extended use cases)

💡 This approach extends the two heaps method to support removal of elements efficiently, useful in sliding window median problems or when deletions are required.

Intuition

Use two heaps as before but add a hash map to mark elements for lazy deletion. When the top of a heap is marked deleted, pop it until the top is valid.

Algorithm

1. Maintain two heaps and a hash map for delayed removals.
2. Add numbers to heaps and balance as usual.
3. When removing a number, mark it in the hash map instead of immediate removal.
4. Clean up top elements of heaps if they are marked deleted before median calculation.

💡 The complexity lies in managing delayed removals and ensuring heaps remain balanced and clean for accurate median retrieval.

</>

Code

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (invert values)
        self.large = []  # min heap
        self.delayed = {}
        self.small_size = 0
        self.large_size = 0

    def _prune(self, heap):
        while heap and self.delayed.get(abs(heap[0]), 0):
            num = abs(heap[0])
            self.delayed[num] -= 1
            if self.delayed[num] == 0:
                del self.delayed[num]
            heapq.heappop(heap)

    def addNum(self, num: int) -> None:
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
            self.small_size += 1
        else:
            heapq.heappush(self.large, num)
            self.large_size += 1

        # Balance heaps
        if self.small_size > self.large_size + 1:
            val = -heapq.heappop(self.small)
            self.small_size -= 1
            heapq.heappush(self.large, val)
            self.large_size += 1
        elif self.large_size > self.small_size:
            val = heapq.heappop(self.large)
            self.large_size -= 1
            heapq.heappush(self.small, -val)
            self.small_size += 1

    def removeNum(self, num: int) -> None:
        self.delayed[num] = self.delayed.get(num, 0) + 1
        if self.small and num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self._prune(self.small)
        else:
            self.large_size -= 1
            if self.large and num == self.large[0]:
                self._prune(self.large)

        # Balance heaps
        if self.small_size > self.large_size + 1:
            val = -heapq.heappop(self.small)
            self.small_size -= 1
            heapq.heappush(self.large, val)
            self.large_size += 1
            self._prune(self.small)
        elif self.large_size > self.small_size:
            val = heapq.heappop(self.large)
            self.large_size -= 1
            heapq.heappush(self.small, -val)
            self.small_size += 1
            self._prune(self.large)

    def findMedian(self) -> float:
        if self.small_size > self.large_size:
            return float(-self.small[0])
        else:
            return (-self.small[0] + self.large[0]) / 2

# This approach is more complex and typically used in sliding window median problems.

Line Notes

self.delayed = {}Hash map to track elements marked for lazy removal.

self.small_size = 0Track valid elements count in max heap.

self.large_size = 0Track valid elements count in min heap.

def _prune(self, heap)Remove elements from heap top if they are marked deleted.

if not self.small or num <= -self.small[0]Decide which heap to add the new number to.

self.small_size += 1Update count of valid elements in max heap.

self.large_size += 1Update count of valid elements in min heap.

self.delayed[num] = self.delayed.get(num, 0) + 1Mark number for lazy removal.

self.small_size -= 1Decrement count when removing from max heap.

self.large_size -= 1Decrement count when removing from min heap.

self._prune(self.small)Clean invalid elements from max heap top.

self._prune(self.large)Clean invalid elements from min heap top.

if self.small_size > self.large_sizeReturn median from max heap if it has more elements.

return (-self.small[0] + self.large[0]) / 2Return average of tops if heaps equal size.

// Due to complexity, Java code omitted here but follows similar logic with TreeMap or HashMap for delayed removals and two PriorityQueues.

Line Notes

This approach is complex and typically implemented with additional data structures like TreeMap for delayed removals.This approach is complex and typically implemented with additional data structures like TreeMap for delayed removals.

// Due to complexity, C++ code omitted here but follows similar logic with unordered_map for delayed removals and two priority_queues.

Line Notes

This approach is complex and typically implemented with additional data structures for delayed removals.This approach is complex and typically implemented with additional data structures for delayed removals.

// Due to complexity, JavaScript code omitted here but requires implementing lazy removal with hash maps and two heaps.

Line Notes

This approach is complex and requires custom heap implementations with lazy removal support.This approach is complex and requires custom heap implementations with lazy removal support.

⏱

Complexity

TimeO(log n) per addNum and removeNum call, O(1) per findMedian call

SpaceO(n) for heaps and hash map

Lazy removal avoids costly direct removals from heaps, maintaining efficient operations.

💡 This approach is more advanced and used when removals are required, such as in sliding window median problems.

Interview Verdict: Accepted / Advanced use case

This method is not required for the basic problem but is important for extended scenarios involving removals.

📊

All Approaches - One-Glance Tradeoffs

💡 The two heaps approach is the best balance of efficiency and complexity and should be coded in most interviews.

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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient and introduce the two heaps approach.Step 4: Code the two heaps solution carefully, explaining heap balancing.Step 5: Test your code with sample inputs and edge cases.Step 6: Discuss possible follow-ups like removals or sliding window medians.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

The interviewer tests your understanding of data structures (heaps), ability to maintain balance and order, and efficiency in handling dynamic data streams.

Common Follow-ups

• How to handle removal of elements? → Use lazy removal with hash maps.
• How to find median in a sliding window? → Combine two heaps with lazy removal.

💡 These follow-ups test your ability to extend the basic solution to more complex real-world scenarios.

🔍

Pattern Recognition

When to Use

1) Need median or middle element dynamically; 2) Data arrives as a stream; 3) Efficient insertion and median retrieval required; 4) Sorting on every insertion is too slow.

Signature Phrases

Find median from data streamAdd numbers dynamicallyReturn median at any time

NOT This Pattern When

Sorting static arrays or finding median of fixed datasets without dynamic insertions

Similar Problems

Sliding Window Median - similar but with removalsKth Largest Element in a Stream - uses heap to track kth largestMedian of Two Sorted Arrays - static arrays, median calculation

Practice

1. Consider the following Python code implementing the bottom-up DP solution for the Burst Balloons problem. What is the final returned value when the input is [3,1,5,8]?

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for i in range(left + 1, right):
                coins = nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]
                dp[left][right] = max(dp[left][right], coins)
    return dp[0][n - 1]

print(maxCoins([3,1,5,8]))

easy

A. 167

B. 144

C. 120

D. 135

Solution

1. Step 1: Trace dp array initialization and boundaries

   Input is extended to [1,3,1,5,8,1]. dp is a 6x6 matrix initialized to 0.

2. Step 2: Compute dp values for increasing subarray lengths

   By iterating length from 2 to 5, dp[0][5] accumulates the maximum coins by considering all bursting orders. The known optimal result for [3,1,5,8] is 167 coins.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known example output [OK]

Hint: Known example output is 167 coins [OK]

Common Mistakes:

• Off-by-one in indices
• Forgetting to add virtual balloons
• Miscomputing dp updates

2. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

3. Examine the following modified code for Largest Rectangle in Histogram. Which line contains a subtle bug that can cause incorrect maximum area calculation?

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= h:'

B. Line with 'height = heights[stack.pop()]'

C. Line with 'width = i - left - 1'

D. Line with 'heights.append(0)'

Solution

1. Step 1: Identify condition in while loop

   The condition uses '>=' which causes bars of equal height to be popped prematurely, merging areas incorrectly.

2. Step 2: Correct condition

   Changing '>=' to '>' ensures bars of equal height remain on stack, preserving correct width calculations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '>=' pops equal height bars too early, causing wrong max area [OK]

Hint: Use '>' not '>=' to avoid premature popping [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscomputing width boundaries
• Forgetting sentinel bar

4. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., transactions can overlap or reuse the same day). Which modification to the DP approach correctly handles this variant?

hard

A. Increase the DP state dimension to track the number of transactions per day and allow multiple buys/sells on the same day

B. Remove the holding state and allow buying and selling at the same index in the DP transitions

C. Use the original DP but allow t to increment multiple times per day to simulate overlapping transactions

D. Switch to a greedy approach summing all positive price differences, ignoring transaction limits

Solution

1. Step 1: Understand the variant's implication

   Allowing multiple buys and sells on the same day means the holding state is no longer needed to prevent overlapping transactions.

2. Step 2: Modify DP transitions accordingly

   Removing the holding state and allowing buy and sell transitions at the same day index enables modeling multiple transactions per day correctly.

3. Step 3: Evaluate other options

   Increasing DP dimensions adds unnecessary complexity; incrementing t multiple times per day breaks the transaction count logic; greedy ignores transaction limits and is incorrect.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Removing holding state fits the relaxed constraint of multiple transactions per day [OK]

Hint: Relax holding state to allow multiple same-day transactions [OK]

Common Mistakes:

• Trying to track multiple transactions per day with extra DP dimensions
• Misusing transaction count increments
• Switching to greedy ignoring constraints

5. Suppose the skyline problem is extended so that buildings can overlap and have negative heights (representing underground structures). Which modification to the divide and conquer algorithm is necessary to correctly handle this variant?

hard

A. No modification needed; the existing merge logic works for negative heights

B. Modify the merge step to consider absolute values of heights when computing max height

C. Use a brute force height map simulation instead, as divide and conquer cannot handle negative heights

D. Adjust the merge step to track both max and min heights at each x-coordinate and merge accordingly

Solution

1. Step 1: Understand negative height impact

   Negative heights mean skyline can go below ground, so max height alone is insufficient.

2. Step 2: Modify merge logic

   Need to track both max and min heights to merge skylines correctly, handling positive and negative overlaps.

3. Step 3: Evaluate options

   Ignoring negative heights or using absolute values breaks correctness; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking both max and min heights handles negative overlaps correctly [OK]

Hint: Negative heights require tracking min as well as max heights [OK]

Common Mistakes:

• Assuming negative heights can be handled as positive
• Ignoring negative heights in merge logic
• Switching to brute force unnecessarily