Largest Rectangle in Histogram

▶

Steps

setup

Initialize stack and max_area

We start with an empty stack and max_area set to 0. The input array is extended by appending a sentinel 0 height to ensure all bars are processed.

💡 Initializing max_area and stack prepares us to track the largest rectangle and the indices of bars in ascending height order.

Line:

stack = []
max_area = 0
heights.append(0)

💡 The sentinel 0 at the end guarantees the stack will be emptied by the end of iteration.

traverse

Start iteration with i=0, height=2

We move to the first bar at index 0 with height 2. Since the stack is empty, we push index 0 onto the stack.

💡 Pushing the first bar index sets the baseline for future comparisons and area calculations.

Line:

for i, h in enumerate(heights):
    # i=0, h=2
    stack.append(i)

💡 Stack maintains indices of bars in ascending height order; pushing index 0 starts this sequence.

compare

Process i=1, height=1; compare with stack top height=2

At index 1, height is 1, which is less than height at stack top index 0 (height 2). We pop index 0 to calculate area.

💡 Encountering a shorter bar triggers popping taller bars to calculate possible rectangle areas.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 Popping taller bars when a shorter bar is found ensures we calculate max areas for bars that can't extend further right.

shrink

Calculate area for popped bar height=2

We calculate area with height 2, width is i - left - 1 = 1 - (-1) - 1 = 1. Area = 2 * 1 = 2. Update max_area to 2.

💡 Calculating area here finds the largest rectangle possible with the popped bar as the smallest height.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 Width calculation uses the index before the popped bar to find the rectangle's left boundary.

insert

Push current index 1 onto stack

After popping taller bars, we push index 1 (height 1) onto the stack.

💡 Pushing the current index maintains the stack's ascending height order for future comparisons.

Line:

stack.append(i)

💡 Stack now holds indices of bars with non-decreasing heights.

traverse

Process i=2, height=5; push since 5 > height at stack top (1)

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

💡 Pushing when current height is greater preserves ascending order in stack.

Line:

stack.append(i)

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

traverse

Process i=3, height=6; push since 6 > height at stack top (5)

At index 3, height 6 is greater than height at stack top index 2 (height 5), so we push index 3 onto the stack.

💡 Continuing to push taller bars keeps stack sorted by height.

Line:

stack.append(i)

💡 Stack now has indices [1, 2, 3] with heights [1, 5, 6].

compare

Process i=4, height=2; pop taller bars from stack

At index 4, height 2 is less than height at stack top index 3 (height 6), so we pop index 3 to calculate area.

💡 Encountering a shorter bar triggers popping taller bars to finalize their max rectangle areas.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 We calculate area for bar at index 3 before pushing current index.

shrink

Calculate area for popped bar height=6

Calculate area with height 6, width = i - left - 1 = 4 - 2 - 1 = 1. Area = 6 * 1 = 6. Update max_area to 6.

💡 Calculating area here finds the largest rectangle with the popped bar as the smallest height.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 Width uses the index before popped bar to find rectangle's left boundary.

compare

Pop next taller bar index 2 (height 5)

Height 2 < height at stack top index 2 (height 5), so pop index 2 to calculate area.

💡 Continue popping taller bars until top bar height ≤ current height.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 Multiple pops can occur for one shorter bar to finalize areas for all taller bars.

shrink

Calculate area for popped bar height=5

Calculate area with height 5, width = i - left - 1 = 4 - 1 - 1 = 2. Area = 5 * 2 = 10. Update max_area to 10.

💡 This area calculation finds the largest rectangle so far, spanning bars at indices 2 and 3.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 Width calculation shows how far the rectangle extends left and right.

insert

Push current index 4 (height 2) onto stack

After popping taller bars, push index 4 onto the stack.

💡 Pushing current index maintains stack order for future iterations.

Line:

stack.append(i)

💡 Stack now contains indices [1,4] with heights [1,2].

traverse

Process i=5, height=3; push since 3 > height at stack top (2)

At index 5, height 3 is greater than height at stack top index 4 (height 2), so push index 5.

💡 Pushing taller bars continues the ascending order in stack.

Line:

stack.append(i)

💡 Stack now has indices [1,4,5] with heights [1,2,3].

prune

Process i=6, height=0 (sentinel); pop all taller bars

At sentinel index 6, height 0 is less than height at stack top index 5 (height 3), so pop index 5 to calculate area.

💡 Sentinel triggers popping all remaining bars to finalize areas.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 Sentinel ensures all bars are processed for max area calculation.

shrink

Calculate area for popped bar height=3

Calculate area with height 3, width = i - left - 1 = 6 - 4 - 1 = 1. Area = 3 * 1 = 3. max_area remains 10.

💡 Area calculation confirms if max_area needs update.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 Some popped bars yield smaller areas, max_area stays unchanged.

prune

Pop next taller bar index 4 (height 2)

Height 0 < height at stack top index 4 (height 2), so pop index 4 to calculate area.

💡 Continue popping until stack top height ≤ current height.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 Popping bars finalizes their max rectangle areas.

shrink

Calculate area for popped bar height=2

Calculate area with height 2, width = i - left - 1 = 6 - 1 - 1 = 4. Area = 2 * 4 = 8. max_area remains 10.

💡 Area calculation checks if max_area should be updated.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 Rectangle spans multiple bars to the left.

prune

Pop last bar index 1 (height 1)

Height 0 < height at stack top index 1 (height 1), so pop index 1 to calculate area.

💡 Final pop to empty stack and calculate area for last bar.

Line:

while stack and heights[stack[-1]] > h:
    height = heights[stack.pop()]

💡 Last bar's area calculation completes the process.

shrink

Calculate area for popped bar height=1

Calculate area with height 1, width = i - left - 1 = 6 - (-1) - 1 = 6. Area = 1 * 6 = 6. max_area remains 10.

💡 Final area calculation confirms max_area is correct.

Line:

left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, height * width)

💡 The last rectangle spans the entire histogram except the sentinel.

reconstruct

Return max_area and restore original array

Iteration ends, sentinel removed restoring original array. max_area 10 is returned as the largest rectangle area.

💡 Returning max_area completes the algorithm with the correct answer.

Line:

heights.pop()
return max_area

💡 The algorithm efficiently found the largest rectangle without brute force.

def largestRectangleArea(heights):
    stack = []  # STEP 1
    max_area = 0  # STEP 1
    heights.append(0)  # STEP 1
    for i, h in enumerate(heights):  # STEP 2
        while stack and heights[stack[-1]] > h:  # STEP 3,8,10,14,16,18
            height = heights[stack.pop()]  # STEP 3,8,10,14,16,18
            left = stack[-1] if stack else -1  # STEP 4,9,11,15,17,19
            width = i - left - 1  # STEP 4,9,11,15,17,19
            max_area = max(max_area, height * width)  # STEP 4,9,11,15,17,19
        stack.append(i)  # STEP 2,5,6,7,12,13
    heights.pop()  # STEP 20
    return max_area  # STEP 20

📊

Largest Rectangle in Histogram - Watch the Algorithm Execute, Step by Step

Watching the stack operations and area calculations visually reveals how the algorithm efficiently finds the largest rectangle without checking all sub-rectangles.

setup

2

0

1

1

5

2

6

3

2

4

3

5

0

6

Result: 0

move_right

stack

2

0

1

1

5

2

6

3

2

4

3

5

0

6

Result: 0

pop

2

0

i

1

1

5

2

6

3

2

4

3

5

0

6

Result: 0

record

2

0

i

1

1

5

2

6

3

2

4

3

5

0

6

Result: 2

move_right

2

0

stack

1

1

5

2

6

3

2

4

3

5

0

6

Result: 2

move_right

2

0

1

1

stack

5

2

6

3

2

4

3

5

0

6

Result: 2

move_right

2

0

1

1

5

2

stack

6

3

2

4

3

5

0

6

Result: 2

pop

2

0

1

1

stack

5

2

6

3

i

2

4

3

5

0

6

Result: 2

record

2

0

1

1

stack

5

2

6

3

i

2

4

3

5

0

6

Result: 6

pop

2

0

stack

1

1

5

2

6

3

i

2

4

3

5

0

6

Result: 6

record

2

0

stack

1

1

5

2

6

3

i

2

4

3

5

0

6

Result: 10

move_right

2

0

1

1

5

2

6

3

stack

2

4

3

5

0

6

Result: 10

move_right

2

0

1

1

5

2

6

3

2

4

stack

3

5

0

6

Result: 10

pop

2

0

1

1

5

2

6

3

stack

2

4

3

5

i

0

6

Result: 10

record

2

0

1

1

5

2

6

3

stack

2

4

3

5

i

0

6

Result: 10

pop

2

0

stack

1

1

5

2

6

3

2

4

3

5

i

0

6

Result: 10

record

2

0

stack

1

1

5

2

6

3

2

4

3

5

i

0

6

Result: 10

pop

2

0

1

1

5

2

6

3

2

4

3

5

i

0

6

Result: 10

record

2

0

1

1

5

2

6

3

2

4

3

5

i

0

6

Result: 10

return

2

0

1

1

5

2

6

3

2

4

3

5

Result: 10

Key Takeaways

✓ The stack maintains indices of bars in ascending height order, enabling efficient area calculations.

This insight is hard to see from code alone because the stack operations and their purpose are implicit without visualization.

✓ Popping bars when a shorter bar is encountered finalizes the largest rectangle for those bars.

Visualizing the popping and area calculation clarifies why the algorithm doesn't need to check all sub-rectangles.

✓ The sentinel 0 height at the end ensures all bars are processed and the stack is emptied.

Without the sentinel, the algorithm would need extra logic to finalize remaining bars; the sentinel simplifies the process.

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. Given the following code snippet implementing the two-pointer approach for trapping rain water, what is the value of the variable water after the first iteration of the while loop when the input is [2, 0, 2]?

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: First iteration of while loop

   height[left]=2, height[right]=2, since height[left] is not less than height[right], else branch runs. height[right]=2 ≥ right_max=0, so right_max=2, right decrements to 1, water remains 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Water not added on first iteration because max updated [OK]

Hint: Water added only when current height < max height on that side [OK]

Common Mistakes:

• Adding water before max height is updated
• Confusing left and right pointer conditions
• Off-by-one errors in pointer movement

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. What is the time complexity of the brute force approach for the trapping rain water problem, where for each bar you find the maximum height to the left and right using nested loops?

medium

A. O(n log n)

B. O(n)

C. O(n^2)

D. O(n^3)

Solution

1. Step 1: Identify loops

   Outer loop runs n times; for each i, two inner loops run up to i and n-i times respectively.

2. Step 2: Calculate total operations

   Each inner loop can run up to O(n), so total is O(n) * O(n) = O(n²).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n elements -> quadratic time [OK]

Hint: Nested loops over n elements -> O(n²) time [OK]

Common Mistakes:

• Confusing with prefix/suffix approach O(n)
• Assuming sorting or log factor involved
• Mistaking inner loops as constant time