Maximal Rectangle (Matrix to Histogram)

▶

Steps

setup

Initialize variables for first row

We start processing the first row of the matrix, initializing the heights array to zeros and max_area to zero.

💡 Initializing heights is crucial because it represents the histogram for the current row, which we will update and analyze.

Line:

max_area = 0
cols = len(matrix[0])
heights = [0] * cols

💡 The heights array will be updated row by row to represent histogram heights of consecutive 1's.

fill_row

Update heights for first row

We update the heights array by scanning the first row. For each '1', we increment height; for '0', reset to zero.

💡 This step converts the first row into a histogram representation, which is the basis for rectangle calculation.

Line:

for i in range(cols):
    heights[i] = heights[i] + 1 if row[i] == '1' else 0

💡 Heights now represent the number of consecutive 1's vertically up to this row.

setup

Start largestRectangleArea for first row histogram

We begin processing the histogram heights for the first row, initializing an empty stack and max_area to zero.

💡 Starting the stack-based histogram processing is key to finding the largest rectangle efficiently.

Line:

stack = []
max_area = 0

💡 Stack will hold indices of bars in ascending height order for area calculation.

fill_cells

Process bar at index 0 with height 1

Current bar height is 1, stack is empty, so we push index 0 onto the stack.

💡 Pushing the first bar sets the base for future rectangle calculations.

Line:

stack.append(i)  # i=0, h=1

💡 Stack now contains index 0 representing height 1, maintaining ascending order.

fill_cells

Process bar at index 1 with height 0

Current bar height is 0, which triggers popping all bars from the stack to calculate areas.

💡 A zero height means no rectangle can extend here, so we finalize areas for previous bars.

Line:

if h == 0:
    while stack:
        height = heights[stack.pop()]
        width = i if not stack else i - stack[-1] - 1
        max_area = max(max_area, height * width)

💡 Popping index 0 calculates area 1*1=1, updating max_area to 1.

fill_cells

Push index 1 with height 0

After popping, we push the current index 1 with height 0 onto the stack.

💡 Even zero height bars are pushed to mark boundaries for future calculations.

Line:

stack.append(i)  # i=1, h=0

💡 Stack now contains index 1 with height 0, maintaining monotonic property.

fill_cells

Process bar at index 2 with height 1

Current height 1 is greater than height at stack top (0), so we push index 2 onto the stack.

💡 Pushing increasing heights keeps the stack monotonic and ready for future pops.

Line:

stack.append(i)  # i=2, h=1

💡 Stack now has indices [1, 2] with heights [0, 1].

fill_cells

Process bar at index 3 with height 0

Current height 0 is less than height at stack top (1), so we pop index 2 and calculate area.

💡 Popping when current height is less reveals maximal rectangles ending before current index.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]
    width = i if not stack else i - stack[-1] - 1
    max_area = max(max_area, height * width)

💡 Area calculated: height=1, width=3-1-1=1, area=1, max_area remains 1.

fill_cells

Push index 3 with height 0

Current height 0 equals height at stack top (0), so no pop; instead, push current index.

💡 Equal heights do not cause popping, preserving monotonic order.

Line:

stack.append(i)  # i=3, h=0

💡 Stack now has indices [1, 3] with heights [0, 0].

fill_cells

Process bar at index 4 with height 0

Current height 0 equals height at stack top (0), so push index 4 onto the stack.

💡 Continuing to push equal heights keeps track of boundaries.

Line:

stack.append(i)  # i=4, h=0

💡 Stack now has indices [1, 3, 4] all with height 0.

fill_cells

Finish first row histogram with appended zero

Append a zero height at the end to pop all remaining bars and finalize max_area for first row.

💡 Appending zero ensures all bars are popped and areas calculated.

Line:

for i, h in enumerate(heights + [0]):

💡 All bars popped, max_area for first row is 1.

fill_row

Update heights for second row

Update heights array for second row by incrementing where '1' and resetting where '0'.

💡 Heights build cumulatively to represent vertical bars of 1's.

Line:

for i in range(cols):
    heights[i] = heights[i] + 1 if row[i] == '1' else 0

💡 Heights now reflect consecutive 1's up to second row.

fill_cells

Process bar at index 0 with height 2

Stack empty, push index 0 with height 2.

💡 Start building stack for new histogram.

Line:

stack.append(i)  # i=0, h=2

💡 Stack contains [0] with height 2.

fill_cells

Process bar at index 1 with height 0

Current height 0 less than height at stack top (2), pop index 0 and calculate area.

💡 Pop to calculate rectangle area for taller bars before current smaller bar.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]
    width = i if not stack else i - stack[-1] - 1
    max_area = max(max_area, height * width)

💡 Area = 2 * 1 = 2, max_area updated to 2.

fill_cells

Push index 1 with height 0

Stack empty, push index 1 with height 0.

💡 Push zero height to mark boundary.

Line:

stack.append(i)  # i=1, h=0

💡 Stack contains [1] with height 0.

fill_cells

Process bar at index 2 with height 2

Current height 2 greater than height at stack top (0), push index 2.

💡 Push increasing height to stack.

Line:

stack.append(i)  # i=2, h=2

💡 Stack contains [1, 2] with heights [0, 2].

fill_cells

Process bar at index 3 with height 1

Current height 1 less than height at stack top (2), pop index 2 and calculate area.

💡 Pop taller bars to calculate maximal rectangles.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]
    width = i if not stack else i - stack[-1] - 1
    max_area = max(max_area, height * width)

💡 Area = 2 * (3 - 1 - 1) = 2 * 1 = 2, max_area remains 2.

fill_cells

Push index 3 with height 1

Push index 3 with height 1 after popping taller bars.

💡 Push current bar to maintain monotonic stack.

Line:

stack.append(i)  # i=3, h=1

💡 Stack contains [1, 3] with heights [0, 1].

fill_cells

Process bar at index 4 with height 1

Current height 1 equals height at stack top (1), push index 4.

💡 Equal heights are pushed to stack to track boundaries.

Line:

stack.append(i)  # i=4, h=1

💡 Stack contains [1, 3, 4] with heights [0, 1, 1].

fill_cells

Finish second row histogram with appended zero

Append zero height to pop all remaining bars and update max_area.

💡 Final pops calculate areas for all bars in stack.

Line:

for i, h in enumerate(heights + [0]):

💡 Popping indices 4, 3, 1 calculates areas; max_area updated to 3.

def largestRectangleArea(heights):
    stack = []  # STEP 3 initialize stack
    max_area = 0
    for i, h in enumerate(heights + [0]):  # STEP 11,20 sentinel zero appended
        if h == 0:  # STEP 5,11,20 zero triggers pops
            while stack:
                height = heights[stack.pop()]  # STEP 5,8,14,17 pop and calc
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
        else:
            while stack and heights[stack[-1]] > h:  # STEP 8,14,17 pop condition
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)  # STEP 4,6,7,9,10,13,15,16,18,19 push
    return max_area

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    max_area = 0  # STEP 1 initialize max_area
    cols = len(matrix[0])
    heights = [0] * cols  # STEP 1 initialize heights
    for row in matrix:
        for i in range(cols):  # STEP 2,12 update heights
            heights[i] = heights[i] + 1 if row[i] == '1' else 0
        max_area = max(max_area, largestRectangleArea(heights))  # STEP 20 update max_area
    return max_area

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
print(maximalRectangle(matrix))  # Output: 6

📊

Maximal Rectangle (Matrix to Histogram) - Watch the Algorithm Execute, Step by Step

Watching each stack push and pop operation helps you understand how the algorithm finds the next smaller element and calculates maximal rectangles without guessing.

no_op

Stack (top→bottom)

empty

no_op

Stack (top→bottom)

empty

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

0

↑ pushed: 0

popElement[1]: 0

Stack (top→bottom)

empty

↓ popped: [0]

Contributes: 1

pushElement[1]: 0

Stack (top→bottom)

1

↑ pushed: 1

pushElement[2]: 1

Stack (top→bottom)

2

1

↑ pushed: 2

popElement[3]: 0

Stack (top→bottom)

1

↓ popped: [2]

Contributes: 1

pushElement[3]: 0

Stack (top→bottom)

3

1

↑ pushed: 3

pushElement[4]: 0

Stack (top→bottom)

4

3

1

↑ pushed: 4

popElement[5]: 0

Stack (top→bottom)

empty

↓ popped: [4, 3, 1]

Contributes: 0

no_op

Stack (top→bottom)

empty

pushElement[0]: 2

Stack (top→bottom)

0

↑ pushed: 0

popElement[1]: 0

Stack (top→bottom)

empty

↓ popped: [0]

Contributes: 2

pushElement[1]: 0

Stack (top→bottom)

1

↑ pushed: 1

pushElement[2]: 2

Stack (top→bottom)

2

1

↑ pushed: 2

popElement[3]: 1

Stack (top→bottom)

1

↓ popped: [2]

Contributes: 2

pushElement[3]: 1

Stack (top→bottom)

3

1

↑ pushed: 3

pushElement[4]: 1

Stack (top→bottom)

4

3

1

↑ pushed: 4

popElement[5]: 0

Stack (top→bottom)

empty

↓ popped: [4, 3, 1]

Contributes: 3

Key Takeaways

✓ The monotonic stack efficiently finds the next smaller bar to the left and right, enabling O(n) largest rectangle calculation.

This insight is hard to see from code alone because the stack operations and area calculations are intertwined and subtle.

✓ Appending a sentinel zero height at the end forces popping all remaining bars, ensuring all rectangles are considered.

This technique avoids special end-of-array handling and is a neat trick to finalize calculations.

✓ Zero heights reset the histogram and cause immediate popping of all bars, showing how the algorithm handles breaks in consecutive 1's.

Seeing zero height trigger pops clarifies how the algorithm segments histograms row by row.

Practice

1. Given the following Python code for asteroid collision, what is the output when the input is [8, -8, 5, -10]?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

print(asteroidCollision([8, -8, 5, -10]))

easy

A. [5, -10]

B. [-10]

C. [8, 5, -10]

D. []

Solution

1. Step 1: Trace collision between 8 and -8

   8 and -8 are equal size but opposite direction, both explode -> stack empty.

2. Step 2: Process 5 and then -10

   5 is pushed; -10 collides with 5, since 10 > 5, 5 pops, -10 remains and is pushed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final stack contains only [-10] after resolving collisions [OK]

Hint: Equal size opposite asteroids both explode [OK]

Common Mistakes:

• Forgetting to pop both equal asteroids
• Appending asteroid after it exploded
• Not handling multiple collisions in while loop

2. Consider the following buggy code for finding the first unique character in a stream. Which line contains the subtle bug that causes incorrect output when duplicates appear?

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        # BUG: Missing removal of duplicates from queue front
        result.append(q[0] if q else '#')
    return result

medium

A. Line where freq[idx] is incremented

B. Line where character is appended to queue

C. Line where result is appended

D. Line where duplicates are removed from queue front (missing here)

Solution

1. Step 1: Identify missing logic

   The code does not remove characters from the queue front when their frequency exceeds 1.

2. Step 2: Understand impact

   Without popping duplicates, the queue front may be a repeated character, causing wrong first unique output.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing while loop to pop duplicates is the bug [OK]

Hint: Always remove duplicates from queue front to maintain correctness [OK]

Common Mistakes:

• Forgetting to pop duplicates from queue front
• Appending duplicates multiple times
• Not handling empty queue case

3. What is the amortized time complexity of the pop operation in the optimal two-stack queue implementation, and why?

medium

A. Amortized O(1) because each element is moved at most once between stacks before being popped.

B. O(log n) due to repeated stack operations during transfer.

C. O(1) worst-case because pop_stack always contains all elements in order.

D. O(n) because elements are transferred from push_stack to pop_stack on every pop.

Solution

1. Step 1: Identify when transfer happens

   Transfer from push_stack to pop_stack happens only when pop_stack is empty.

2. Step 2: Analyze element movement

   Each element is pushed and popped at most twice (once into push_stack, once into pop_stack), so total operations per element are constant.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per pop due to limited transfers [OK]

Hint: Each element moves stacks once -> amortized O(1) pop [OK]

Common Mistakes:

• Thinking transfer happens every pop -> O(n) pop
• Assuming worst-case O(1) pop always

4. What is the time complexity of the optimal monotonic stack solution for the Largest Rectangle in Histogram problem, and why?

medium

A. O(n) because each bar is pushed and popped at most once from the stack

B. O(n) but with O(n^2) worst-case due to stack operations

C. O(n^2) because nested loops are used to find boundaries

D. O(n log n) because each element is pushed and popped multiple times

Solution

1. Step 1: Analyze stack operations

   Each bar is pushed once and popped at most once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops over all elements

   Loops run linearly, no repeated scanning of all elements inside inner loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity due to amortized stack operations [OK]

Hint: Each element pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming stack operations cause O(n log n) or O(n^2)
• Confusing nested loops in brute force with stack approach

5. Suppose the problem is modified so that the array is circular and you want to find the next greater element allowing repeated reuse of elements (i.e., you can wrap around multiple times). Which modification to the monotonic stack approach correctly handles this variant?

hard

A. Modify the stack to store values instead of indices to handle repeated reuse

B. Use a brute force nested loop with modulo indexing to simulate infinite wrap

C. Extend the doubled array to triple or more copies and run the same monotonic stack algorithm

D. Use a queue instead of a stack to process elements in order for multiple wraps

Solution

1. Step 1: Understand problem variant

   Allowing repeated reuse means next greater element might appear after multiple wraps, not just one.

2. Step 2: Modify approach accordingly

   Extending the array to triple or more copies simulates multiple wraps, allowing monotonic stack to find next greater elements beyond one wrap.

3. Step 3: Why other options fail

   Brute force is inefficient; storing values loses index mapping; queue does not maintain monotonic property needed.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Extending array copies simulates multiple wraps correctly [OK]

Hint: Multiple wraps -> extend array copies accordingly [OK]

Common Mistakes:

• Using brute force which is inefficient
• Storing values instead of indices losing position info
• Replacing stack with queue losing monotonic property