Largest Rectangle in Histogram Using Stack in DSA Python - Execution Trace

Concept Flow - Largest Rectangle in Histogram Using Stack

Start with empty stack

↓

Iterate over bars by index

↓

While stack not empty and current bar height < height at stack top

↓

Pop from stack

↓

Calculate area with popped bar as smallest

↓

Update max area if needed

↓

Push current index to stack

↓

After iteration, pop remaining bars

↓

Calculate area for each popped bar

↓

Update max area if needed

↓

Return max area

We scan bars left to right, using a stack to keep indexes of bars in ascending height. When a lower bar appears, we pop taller bars to calculate areas, updating max area.

Execution Sample

DSA Python

def largest_rectangle(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights):
        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)
        stack.append(i)
    while stack:
        height = heights[stack.pop()]
        width = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)
    return max_area

Calculates largest rectangle area in histogram by using a stack to track bars and computing areas when a smaller bar is found.

Execution Table

Step	Operation	Current Index	Stack Before	Stack After	Area Calculated	Max Area	Visual State
1	Start	-	[]	[]	-	0	[]
2	Push index 0 (height 2)	0	[]	[0]	-	0	[2]
3	Current height 1 < height at stack top (2), pop index 0	1	[0]	[]	2 * 1 = 2	2	[]
4	Push index 1 (height 1)	1	[]	[1]	-	2	[1]
5	Current height 5 > stack top height 1, push index 2	2	[1]	[1,2]	-	2	[1,5]
6	Current height 6 > stack top height 5, push index 3	3	[1,2]	[1,2,3]	-	2	[1,5,6]
7	Current height 2 < stack top height 6, pop index 3	4	[1,2,3]	[1,2]	6 * (4-2-1)=6	6	[1,5]
8	Current height 2 < stack top height 5, pop index 2	4	[1,2]	[1]	5 * (4-1-1)=10	10	[1]
9	Current height 2 > stack top height 1, push index 4	4	[1]	[1,4]	-	10	[1,2]
10	Current height 3 > stack top height 2, push index 5	5	[1,4]	[1,4,5]	-	10	[1,2,3]
11	End of array reached, pop remaining stack, pop index 5	-	[1,4,5]	[1,4]	3 * (6-4-1)=3	10	[1,2]
12	Pop index 4	-	[1,4]	[1]	2 * (6-1-1)=8	10	[1]
13	Pop index 1	-	[1]	[]	1 * 6 = 6	10	[]
14	Return max area	-	[]	[]	-	10	[]

💡 All bars processed and stack emptied, max area found is 10

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	Final
stack	[]	[0]	[]	[1]	[1,2]	[1,2,3]	[1,2]	[1]	[1,4]	[1,4,5]	[1,4]	[1]	[]	[]
max_area	0	0	2	2	2	2	6	10	10	10	10	10	10	10
current_index	-	0	1	1	2	3	4	4	4	5	-	-	-	-

Key Moments - 3 Insights

Why do we pop from the stack when the current bar is lower than the bar at the stack's top?

Because the current lower bar means the previous taller bars cannot extend further right, so we calculate the area for those bars now (see steps 7 and 8 in execution_table).

How do we calculate the width for the popped bar's rectangle?

Width is the distance between the current index and the index on the new top of the stack after popping, minus one. If stack is empty, width is current index (or total length at end). See steps 7,8,12 in execution_table.

Why do we process remaining bars in the stack after finishing the iteration?

Because those bars extend to the end of the histogram, so we calculate their areas using the total length as right boundary (see steps 11-13).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the max_area after popping index 2?

A 10

B 8

C 6

D 12

💡 Hint

Check the 'Max Area' column at step 8 in execution_table.

At which step does the stack become empty for the first time?

A Step 12

B Step 13

C Step 14

D Step 10

💡 Hint

Look at the 'Stack After' column to find when it changes to [].

If the input histogram had all bars of equal height, how would the max_area compare to the number of bars?

A max_area equals number of bars only

B max_area equals height only

C max_area equals height times number of bars

D max_area is zero

💡 Hint

Refer to variable_tracker and think about how width is calculated when stack is never popped early.

Concept Snapshot

Largest Rectangle in Histogram Using Stack:
- Use a stack to store indices of bars in ascending height.
- Iterate bars, pop stack when current bar is lower to calculate area.
- Calculate width using current index and stack top after pop.
- After iteration, pop remaining bars to calculate areas.
- Max area updated during pops, final max area returned.

Full Transcript

This concept finds the largest rectangle area in a histogram using a stack. We keep indices of bars in ascending order. When a lower bar appears, we pop taller bars to calculate areas with those bars as the smallest height. Width is calculated based on current index and the new top of the stack. After processing all bars, we pop remaining bars to calculate their areas considering the histogram's end. The maximum area found during these steps is returned as the result.

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To reverse the order of bars for easier calculation

B. To store the heights of all bars in sorted order

C. To keep track of bars' indices with increasing heights

D. To count the total number of bars in the histogram

Solution

1. Step 1: Understand the role of the stack

   The stack is used to store indices of bars in increasing height order to efficiently find the largest rectangle.

2. Step 2: Explain why increasing order is important

   When a bar with smaller height appears, we pop from the stack to calculate areas with bars taller than the current one.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option C

4. Quick Check:

   Stack stores indices in increasing height order [OK]

Hint: Stack stores indices of increasing height bars [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars by height
• Using stack to count bars instead of track indices

2. Which of the following Python code snippets correctly initializes an empty stack for the Largest Rectangle in Histogram algorithm?

easy

A. stack = ()

B. stack = {}

C. stack = None

D. stack = []

Solution

1. Step 1: Identify correct data structure for stack

   In Python, a list is commonly used as a stack because it supports append() and pop() operations.

2. Step 2: Check each option

   stack = [] uses a list ([]), which is correct. stack = {} uses a dictionary ({}), not suitable. stack = None assigns None, not a stack. stack = () uses a tuple (()), which is immutable.

3. Final Answer:

   stack = [] -> Option D

4. Quick Check:

   List [] is correct stack initialization [OK]

Hint: Use list [] for stack in Python [OK]

Common Mistakes:

• Using dictionary {} instead of list
• Using tuple () which is immutable
• Assigning None instead of a list

3. What is the output of the following code snippet for the histogram heights = [2, 1, 5, 6, 2, 3]?

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        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)
        stack.append(i)
    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

medium

A. 10

B. 12

C. 8

D. 6

Solution

1. Step 1: Trace the stack and area calculation

   Iterate through heights with an extra 0 at the end to pop all bars. The largest rectangle area found is 10 (from bars with heights 5 and 6).

2. Step 2: Confirm max area calculation

   The max area is calculated as max(10, others), so final answer is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Add zero height at end to pop all bars [OK]

Common Mistakes:

• Forgetting to add zero at end of heights
• Incorrect width calculation
• Not popping all bars from stack

4. Find the error in this code snippet for Largest Rectangle in Histogram:

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

medium

A. Width calculation should be i - stack[-1] - 1

B. Missing adding zero height at end of heights

C. Comparison should be > instead of >=

D. Stack should store heights, not indices

Solution

1. Step 1: Identify width calculation mistake

   Width is calculated as i - stack[-1], but it should be i - stack[-1] - 1 to exclude the popped bar's index.

2. Step 2: Confirm other parts

   Adding zero at end is optional but common; comparison >= is acceptable; stack stores indices correctly.

3. Final Answer:

   Width calculation should be i - stack[-1] - 1 -> Option A

4. Quick Check:

   Width = i - stack[-1] - 1 [OK]

Hint: Width = current index - previous stack top - 1 [OK]

Common Mistakes:

• Incorrect width calculation causing wrong area
• Forgetting to add zero at end (optional)
• Confusing stack contents (indices vs heights)

5. Given the histogram heights = [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach?

hard

A. 10

B. 15

C. 12

D. 8

Solution

1. Step 1: Use stack to find largest rectangle

   Traverse bars with an extra 0 at end. The largest rectangle is formed by heights 5, 4, 5 spanning width 3, area = 12, but a larger rectangle is formed by heights 6 spanning width 2, area = 12, and also by heights 6 spanning width 1, area = 6. However, the maximum area is 15 formed by heights 5, 4, 5, 1, 6 combined correctly.

2. Step 2: Confirm no larger area exists

   After careful calculation, the largest rectangle area is 15 (from bars at indices 2 to 4 with height 5).

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Max area = 15 from bars 5,4,5 [OK]

Hint: Check rectangles formed by popped bars for max area [OK]

Common Mistakes:

• Ignoring width when calculating area
• Not adding zero height at end to pop all bars
• Miscomputing width boundaries