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. Given the following code for largestRectangleArea, what is the returned max_area for input heights = [2,1,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace stack operations for heights=[2,1,2]

   i=0,h=2: stack=[0]; i=1,h=1: pop 0 (height=2,width=1), max_area=2; stack=[]; append 1; i=2,h=2: append 2; i=3,h=0: pop 2 (height=2,width=1), max_area=2; pop 1 (height=1,width=3), max_area=3

2. Step 2: Final max_area after processing all elements

   max_area=3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max rectangle area is 3 for input [2,1,2] [OK]

Hint: Remember to add sentinel zero to flush stack [OK]

Common Mistakes:

• Forgetting sentinel zero causes missed areas
• Incorrect width calculation
• Off-by-one in stack indices

2. Consider the following Python code implementing the optimal solution for Next Greater Element II. What is the final output when the input is [1, 2, 1]?

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    doubled = nums + nums
    answer = [-1] * n
    stack = []
    for i, num in enumerate(doubled):
        while stack and doubled[stack[-1]] < num:
            idx = stack.pop()
            if idx < n:
                answer[idx] = num
        if i < n:
            stack.append(i)
    return answer

print(nextGreaterElements([1,2,1]))

easy

A. [-1, 2, -1]

B. [2, -1, 2]

C. [2, 1, 2]

D. [2, 2, 2]

Solution

1. Step 1: Trace stack and answer updates

   Initially, stack is empty. Iterate over doubled = [1,2,1,1,2,1]. - i=0, num=1: stack=[0] - i=1, num=2: 1 < 2, pop 0, answer[0]=2, stack=[]; push 1 -> stack=[1] - i=2, num=1: 2 > 1, push 2 -> stack=[1,2] - i=3, num=1: push 3 (ignored since i≥n) - i=4, num=2: pop 2 (answer[2]=2), pop 1 (answer[1]=2), stack=[] - i=5, num=1: push 5 (ignored)

2. Step 2: Final answer array

   answer = [2, -1, 2] because answer[1] was updated only when popping index 1 at i=4, but since i=4≥n, answer update only occurs if idx < n, so answer[1] remains -1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected next greater elements for circular array [OK]

Hint: Stack pops update answer only for indices < n [OK]

Common Mistakes:

• Updating answer for indices ≥ n causing duplicates
• Misreading when to push indices onto stack
• Confusing values and indices in stack

3. What is the time complexity of the getMin() operation in the single stack with encoded minimum values approach for the Minimum Stack problem, and why?

medium

A. O(1), because the minimum value is stored and updated during push and pop operations.

B. O(n), because it needs to scan the entire stack to find the minimum.

C. O(log n), because the stack maintains a balanced structure to track minimums.

D. O(n), because the encoded differences require decoding all elements to find the minimum.

Solution

1. Step 1: Understand getMin() operation

   In the encoded stack approach, minVal is updated on every push/pop, so getMin() just returns minVal.

2. Step 2: Analyze complexity

   Since getMin() returns a stored variable without iteration, it runs in O(1) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   getMin() is a direct variable access, no loops [OK]

Hint: getMin() returns stored minVal updated on push/pop [OK]

Common Mistakes:

• Assuming getMin scans stack
• Confusing encoded values require decoding
• Thinking balanced tree needed for min tracking

4. Suppose the problem is modified so that the input string can contain not only '(' and ')' but also '*' characters, where '*' can represent either '(' or ')' or an empty string. Which approach is best suited to handle this variant efficiently?

hard

A. Use dynamic programming to track valid substring lengths considering '*' as wildcards.

B. Use the two-pass counter approach ignoring '*' characters.

C. Use brute force checking all substrings and validating with '*' replacements.

D. Use a stack-based approach tracking indices and possible '*' substitutions.

Solution

1. Step 1: Understand the complexity introduced by '*'

   The '*' character can represent multiple possibilities, requiring tracking multiple states.

2. Step 2: Evaluate approaches for handling wildcards

   Dynamic programming can efficiently track valid substring lengths considering '*' as '(', ')' or empty, unlike counters or naive stack approaches.

3. Step 3: Rule out brute force due to exponential possibilities

   Brute force checking all substrings with '*' replacements is infeasible for large inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles wildcard substitutions efficiently [OK]

Hint: DP handles wildcard '*' efficiently [OK]

Common Mistakes:

• Ignoring '*' in counters
• Assuming stack alone can handle wildcards
• Trying brute force for large inputs

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