Find Median from Data Stream

▶

Steps

setup

Initialize MedianFinder

Create empty max heap 'small' and min heap 'large', initialize delayed removals map and size counters.

💡 Starting with empty heaps and counters sets the foundation for adding numbers and balancing heaps.

Line:

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

💡 Heaps and counters are ready to track numbers and maintain balance.

insert

Add number 1 to 'small' heap

Since 'small' is empty, add 1 to 'small' as -1 (max heap stores negatives). Increment small_size.

💡 First number goes to 'small' heap to start building the data structure.

Line:

if not self.small or num <= -self.small[0]:
    heapq.heappush(self.small, -num)
    self.small_size += 1

💡 The first number always goes to 'small' heap to start balancing.

insert

Add number 2 to 'large' heap

Number 2 is greater than -small[0] (which is 1), so add 2 to 'large' heap and increment large_size.

💡 Numbers greater than the max of 'small' go to 'large' heap to keep order.

Line:

else:
    heapq.heappush(self.large, num)
    self.large_size += 1

💡 Splitting numbers between heaps keeps them balanced and ordered.

shrink

Balance heaps after adding 2

Heaps are balanced: small_size=1, large_size=1, difference is 0, so no rebalancing needed.

💡 Balancing ensures heaps differ in size by at most 1 for correct median calculation.

Line:

if self.small_size > self.large_size + 1:
    ...
elif self.large_size > self.small_size:
    ...

💡 Balanced heaps mean median can be computed from tops directly.

compare

Find median after adding 1 and 2

Since both heaps have equal size, median is average of tops: (1 + 2) / 2 = 1.5.

💡 Median for even count is average of max of 'small' and min of 'large'.

Line:

if self.small_size == self.large_size:
    median = (-self.small[0] + self.large[0]) / 2

💡 Median depends on top elements of both heaps when sizes match.

insert

Add number 3 to 'large' heap

Number 3 is greater than -small[0] (1), so add 3 to 'large' heap and increment large_size.

💡 New number goes to 'large' because it is greater than max of 'small'.

Line:

else:
    heapq.heappush(self.large, num)
    self.large_size += 1

💡 Adding to 'large' may unbalance heaps, requiring rebalancing.

shrink

Balance heaps after adding 3

Since large_size (2) > small_size (1), move smallest from 'large' (2) to 'small' as -2. Update sizes accordingly.

💡 Balancing keeps heaps sizes within 1 to maintain median correctness.

Line:

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

💡 Rebalancing moves elements between heaps to maintain size property.

compare

Find median after adding 3

Now small_size (2) > large_size (1), median is top of 'small' heap: 2 (negate -2).

💡 Median for odd count is top of larger heap.

Line:

else:
    median = -self.small[0]

💡 Median depends on heap sizes and top elements.

reconstruct

Summary: Median after first findMedian call

Median after adding 1 and 2 is 1.5, computed from tops of both heaps.

💡 Shows how median is derived from balanced heaps with even count.

Line:

return median

💡 Median calculation depends on heap sizes and top elements.

reconstruct

Summary: Median after second findMedian call

Median after adding 3 is 2, the top of 'small' heap which has more elements.

💡 Shows median for odd count from the larger heap top.

Line:

return median

💡 Median is the middle element when count is odd.

import heapq

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

    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]:  # STEP 2,6
            heapq.heappush(self.small, -num)  # STEP 2,6
            self.small_size += 1  # STEP 2,6
        else:
            heapq.heappush(self.large, num)  # STEP 3,6
            self.large_size += 1  # STEP 3,6

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

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

    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

📊

Find Median from Data Stream - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the two heaps maintain a balanced state to efficiently find the median at any point in the data stream.

setup

insert

small_top

-1

0

insert

small_top

-1

0

large_top

2

1

compare

small_top

-1

0

large_top

2

1

compare

small_top

-1

0

large_top

2

1

Result: 1.5

insert

small_top

-1

0

large_top

2

1

3

2

Result: 1.5

rebalance

small_top

-2

0

-1

1

large_top

3

2

Result: 1.5

compare

small_top

-2

0

-1

1

large_top

3

2

Result: 2

record

small_top

-1

0

large_top

2

1

Result: 1.5

record

small_top

-2

0

-1

1

large_top

3

2

Result: 2

Key Takeaways

✓ Two heaps maintain a balanced partition of the data stream to efficiently compute median.

This balance is hard to see from code alone but is clear when watching heaps grow and shrink.

✓ Median calculation depends on heap sizes: average of tops if equal, top of larger heap if odd count.

Visualizing heap sizes and top elements clarifies why median formulas differ.

✓ Rebalancing moves elements between heaps to maintain size constraints after each insertion.

Seeing the actual element moved during rebalance helps understand the heap size invariants.

Practice

1. Consider the following Python code implementing the optimal DP solution for the stock problem with k transactions. What is the final output when calling maxProfit(1, [1, 5, 2])?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

print(maxProfit(1, [1, 5, 2]))

easy

A. 4

B. 5

C. 3

D. 1

Solution

1. Step 1: Trace dp for i=2 (price=2), t=1

   Initialize next_dp and curr_dp with zeros. At i=2, curr_dp[1][0] = max(-2 + next_dp[1][1], next_dp[1][0]) = max(-2 + 0, 0) = 0; curr_dp[1][1] = max(2 + next_dp[0][0], next_dp[1][1]) = max(2 + 0, 0) = 2.

2. Step 2: Trace dp for i=1 (price=5), t=1

   curr_dp[1][0] = max(-5 + next_dp[1][1], next_dp[1][0]) = max(-5 + 2, 0) = 0; curr_dp[1][1] = max(5 + next_dp[0][0], next_dp[1][1]) = max(5 + 0, 2) = 5.

3. Step 3: Trace dp for i=0 (price=1), t=1

   curr_dp[1][0] = max(-1 + next_dp[1][1], next_dp[1][0]) = max(-1 + 5, 0) = 4; curr_dp[1][1] = max(1 + next_dp[0][0], next_dp[1][1]) = max(1 + 0, 5) = 5.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Maximum profit with 1 transaction is buying at 1 and selling at 5 -> profit 4 [OK]

Hint: Trace dp arrays backward to find max profit [OK]

Common Mistakes:

• Confusing holding and not holding states
• Off-by-one errors in indexing transactions
• Misreading the final dp state to return

2. You need to transform one string into another using the minimum number of insertions, deletions, and substitutions. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy algorithm that replaces characters whenever they differ

B. Pure brute force recursion without memoization

C. Dynamic Programming that builds a table of subproblem solutions based on prefixes

D. Divide and conquer by splitting strings into halves and solving independently

Solution

1. Step 1: Understand problem requires minimum edits

   The problem asks for minimum insertions, deletions, and substitutions to convert one string to another, which is a classic DP problem.

2. Step 2: Identify approach guaranteeing optimal substructure

   Dynamic Programming builds solutions for prefixes and combines them, ensuring optimality and polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP table approach is standard for edit distance [OK]

Hint: Edit distance requires DP over prefixes [OK]

Common Mistakes:

• Thinking greedy or divide-and-conquer works optimally

3. You are given two sorted arrays and need to find the median of their combined elements efficiently without fully merging them. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge both arrays completely and then find the median from the merged array.

B. Use binary search to partition the smaller array and find the correct partition in the other array.

C. Use a two-pointer approach to partially merge elements until the median position is reached.

D. Apply dynamic programming to store medians of subarrays and combine results.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the median of two sorted arrays without fully merging them to achieve better than O(m+n) time.

2. Step 2: Identify the optimal approach

   Binary search on the smaller array to find a partition that balances elements on both sides guarantees O(log(min(m,n))) time, which is optimal.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on partition is the known optimal solution [OK]

Hint: Optimal median uses binary search on smaller array [OK]

Common Mistakes:

• Assuming full merge is necessary
• Using two pointers without binary search
• Confusing DP with median finding

4. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

medium

A. Line appending operator '+': path.append('+')

B. Line checking for leading zero: if i != index and num[index] == '0': break

C. Line converting substring to int: curr = int(curr_str)

D. Line resetting path after recursion: path[:] = path[:length_before]

Solution

1. Step 1: Identify handling of leading zeros

   The check for leading zeros is inside the else block, after the first index, which is correct placement.

2. Step 2: Confirm correctness of the check

   The condition "if i != index and num[index] == '0': break" prevents numbers like "05" but is placed after the first index check, which causes it to be skipped for the very first number, allowing invalid leading zeros there.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Leading zero check must be before substring parsing to avoid invalid numbers [OK]

Hint: Leading zero check must be before int conversion and recursion [OK]

Common Mistakes:

• Placing leading zero check too late
• Not breaking early on invalid substrings

5. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output by adding redundant points or missing height changes?

medium

A. Line where maxH is computed with max(h1, h2)

B. Line where merged appends [x, maxH] without checking last height

C. Line where i and j are incremented in the else block

D. Line where h1 and h2 are initialized to 0 at the start

Solution

1. Step 1: Identify the bug

   The code appends every point without checking if the height changed, causing redundant points.

2. Step 2: Correct approach

   Appending should happen only if merged is empty or last height differs from maxH to avoid duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending unconditionally causes redundant points [OK]

Hint: Check if last height differs before appending new point [OK]

Common Mistakes:

• Appending points even if height unchanged
• Incorrectly incrementing indices causing skips
• Not initializing heights properly