Largest Rectangle in Histogram Using Stack in DSA Go - 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 and calculate area

↓

Return max area

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

Execution Sample

DSA Go

heights := []int{2,1,5,6,2,3}
stack := []int{}
maxArea := 0
for i := 0; i <= len(heights); i++ {
  // process bars and stack
}

This code finds the largest rectangle area in the histogram by using a stack to track bars and calculating areas when a smaller bar is found.

Execution Table

Step	Operation	Current Index	Stack Content (indexes)	Popped Index	Calculated Area	Max Area	Visual State (Heights with stack top marked)
1	Push index	0	[0]	None	None	0	2* (stack top)
2	Current bar height 1 < height at stack top 2, pop	1	[]	0	2*1=2	2	1 (current)
3	Push index	1	[1]	None	None	2	1* (stack top)
4	Push index	2	[1,2]	None	None	2	1,5* (stack top)
5	Push index	3	[1,2,3]	None	None	2	1,5,6* (stack top)
6	Current bar height 2 < height at stack top 6, pop	4	[1,2]	3	6*1=6	6	1,5 (stack top)
7	Current bar height 2 < height at stack top 5, pop	4	[1]	2	5*2=10	10	1 (stack top)
8	Push index	4	[1,4]	None	None	10	1,2* (stack top)
9	Push index	5	[1,4,5]	None	None	10	1,2,3* (stack top)
10	Reached end, pop remaining index 5	6	[1,4]	5	3*1=3	10	1,2 (stack top)
11	Pop index 4	6	[1]	4	2*4=8	10	1 (stack top)
12	Pop index 1	6	[]	1	1*6=6	10	empty stack
13	End	6	[]	None	None	10	Final max area

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

Variable Tracker

Variable	Start	After Step 1	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	Final
stack	[]	[0]	[]	[1]	[1,2]	[1,2,3]	[1,2]	[1]	[1,4]	[1,4,5]	[1,4]	[1]	[]	[]
maxArea	0	0	2	2	2	2	6	10	10	10	10	10	10	10
currentIndex	0	0	1	2	3	4	4	4	5	5	6	6	6	6

Key Moments - 3 Insights

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

Because the current lower bar means the rectangle with the height of the bar at the stack top can't extend further right. We calculate area using the popped bar as the smallest height (see steps 6 and 7 in execution_table).

Why do we push the current index after popping bars?

After popping taller bars, we push the current index to mark the start of a new potential rectangle with the current bar's height (see steps 3, 4, 5, 8, 9). This keeps stack heights in ascending order.

Why do we pop remaining bars after finishing the iteration?

Remaining bars in the stack mean their rectangles extend to the end of the histogram. We pop them to calculate areas considering the histogram's full length (see steps 10-12).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the calculated area and why?

A 5 * 2 = 10, because the popped bar height is 5 and width is 2

B 6 * 1 = 6, because the popped bar height is 6 and width is 1

C 2 * 5 = 10, because the popped bar height is 2 and width is 5

D 3 * 3 = 9, because the popped bar height is 3 and width is 3

💡 Hint

Check the 'Calculated Area' and 'Popped Index' columns at step 7 in execution_table

At which step does the maxArea first update to 6?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Max Area' column in execution_table and find when it changes from 2 to 6

If the input histogram was strictly increasing heights, how would the stack content change during iteration?

A Stack would keep growing with all indexes pushed, no popping until end

B Stack would pop every time a new bar is added

C Stack would be empty after each iteration

D Stack would only contain the first index

💡 Hint

Refer to variable_tracker stack values and think about when popping happens (only when current bar is lower)

Concept Snapshot

Largest Rectangle in Histogram Using Stack:
- Use a stack to store indexes of bars in ascending height order
- Iterate bars, pop stack when current bar is lower to calculate area
- Calculate area with popped bar as smallest height
- Update max area during pops
- After iteration, pop remaining bars to finalize max area
- Time complexity: O(n), Space: O(n)

Full Transcript

This visualization shows how to find the largest rectangle in a histogram using a stack. We keep indexes of bars in ascending order on the stack. When a lower bar appears, we pop taller bars to calculate rectangle areas with those bars as the smallest height. We update the maximum area found so far. After processing all bars, we pop any remaining bars to calculate areas extending to the histogram's end. The stack helps track boundaries efficiently, making the algorithm run in linear time. The execution table traces each step, showing stack changes, popped bars, calculated areas, and max area updates. The variable tracker shows how stack and max area evolve. Key moments clarify why popping happens and why we push indexes. The quiz tests understanding of these steps and stack behavior.

Practice

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

easy

A. To sort the histogram bars by height

B. To store the maximum area found so far

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

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand stack usage

   The stack stores indices of bars in increasing height order to find boundaries efficiently.

2. Step 2: Purpose in algorithm

   This helps quickly calculate the largest rectangle when a smaller height bar is found.

3. Final Answer:

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

4. Quick Check:

   Stack tracks increasing bars = B [OK]

Hint: Stack stores indices of increasing heights [OK]

Common Mistakes:

• Thinking stack sorts bars by height
• Using stack to store areas instead of indices
• Ignoring the order of bars in stack

2. Which Go syntax correctly declares a stack to hold indices for the histogram bars?

easy

A. var stack []int

B. stack := make(map[int]int)

C. stack := []string{}

D. var stack int

Solution

1. Step 1: Identify stack type

   The stack holds indices, which are integers, so it should be a slice of int.

2. Step 2: Check syntax correctness

   "var stack []int" declares an empty slice of int, suitable for stack operations.

3. Final Answer:

   var stack []int -> Option A

4. Quick Check:

   Stack as []int slice = C [OK]

Hint: Use slice of int for stack indices [OK]

Common Mistakes:

• Using map instead of slice for stack
• Declaring stack as int instead of slice
• Using string slice for integer indices

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

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    for i := 0; i <= len(heights); i++ {
        var h int
        if i == len(heights) {
            h = 0
        } else {
            h = heights[i]
        }
        for len(stack) > 0 && h < heights[stack[len(stack)-1]] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            var width int
            if len(stack) == 0 {
                width = i
            } else {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

fmt.Println(largestRectangleArea([]int{2, 1, 5, 6, 2, 3}))

medium

A. 6

B. 12

C. 8

D. 10

Solution

1. Step 1: Trace stack and area calculation

   Process bars: max area found is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm max area

   No larger rectangle found; 10 is the largest rectangle area.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max of all popped rectangles [OK]

Common Mistakes:

• Forgetting to add a zero height bar at end
• Incorrect width calculation after popping stack
• Not updating maxArea correctly

4. Identify the bug in this Go code snippet for Largest Rectangle in Histogram:

for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
        height := heights[stack[len(stack)-1]]
        stack = stack[:len(stack)-1]
        width := i
        if len(stack) > 0 {
            width = i - stack[len(stack)-1] - 1
        }
        area := height * width
        if area > maxArea {
            maxArea = area
        }
    }
    stack = append(stack, i)
}
return maxArea

medium

A. Loop should run until i <= len(heights) with a sentinel zero height

B. Width calculation is incorrect when stack is empty

C. Stack should store heights, not indices

D. maxArea should be reset inside the loop

Solution

1. Step 1: Check loop boundary

   The loop misses processing the last bars fully without a sentinel zero height at the end.

2. Step 2: Fix loop to include sentinel

   Loop should run until i <= len(heights) and treat i == len(heights) as height 0 to pop all remaining bars.

3. Final Answer:

   Loop should run until i <= len(heights) with a sentinel zero height -> Option A

4. Quick Check:

   Loop boundary with sentinel zero fixes bug [OK]

Hint: Add sentinel zero height to process all bars [OK]

Common Mistakes:

• Not adding sentinel zero height
• Incorrect width calculation when stack empty
• Resetting maxArea inside loop incorrectly

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

hard

A. 12

B. 15

C. 8

D. 10

Solution

1. Step 1: Analyze bars and stack operations

   Largest rectangle is formed by bars with min height 5 spanning width 3 (indices 2 to 4: heights 5,4,5), area = 5*3 = 15.

2. Step 2: Confirm no larger area

   Other rectangles like 4*3=12 or 2*5=10 are smaller; 15 is maximum.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Max rectangle area = 15 [OK]

Hint: Check width between popped bars for max area [OK]

Common Mistakes:

• Calculating width incorrectly
• Missing wider rectangle spanning multiple bars
• Not popping all bars at the end