Largest Rectangle in Histogram Using Stack in DSA Go

Mental Model

We use a stack to keep track of bars in increasing height order to find the largest rectangle efficiently.

Analogy: Imagine stacking books by height on a shelf. When a shorter book comes, you remove taller books to find the biggest flat space you can make between them.

Histogram bars: height array
[2] [1] [5] [6] [2] [3]
Stack stores indices of bars with increasing heights -> helps find max rectangle.

Dry Run Walkthrough

Input: histogram heights: [2, 1, 5, 6, 2, 3]

Goal: Find the largest rectangle area that can be formed in the histogram

Step 1: Push index 0 (height 2) onto stack

Stack: [0]
Heights: 2 ↑1 5 6 2 3

Why: Start with first bar, stack empty means push it

Step 2: Current height 1 < height at stack top 2, pop index 0 and calculate area

Stack: []
Calculate area with height 2 and width 1 -> area=2
Push index 1

Why: Found smaller bar, so previous taller bar's max rectangle ends here

Step 3: Push index 2 (height 5) since 5 > 1

Stack: [1, 2]
Heights: 2 1 ↑5 6 2 3

Why: Maintain increasing heights in stack

Step 4: Push index 3 (height 6) since 6 > 5

Stack: [1, 2, 3]
Heights: 2 1 5 ↑6 2 3

Why: Keep increasing order

Step 5: Current height 2 < height at stack top 6, pop index 3 and calculate area

Stack: [1, 2]
Calculate area with height 6 and width 1 -> area=6

Why: Smaller bar ends rectangle for taller bar

Step 6: Current height 2 < height at stack top 5, pop index 2 and calculate area

Stack: [1]
Calculate area with height 5 and width 2 -> area=10

Why: Pop taller bars until stack top height ≤ current height

Step 7: Push index 4 (height 2)

Stack: [1, 4]
Heights: 2 1 5 6 ↑2 3

Why: Push current bar after popping taller bars

Step 8: Push index 5 (height 3) since 3 > 2

Stack: [1, 4, 5]
Heights: 2 1 5 6 2 ↑3

Why: Maintain increasing order

Step 9: Reached end, pop remaining bars and calculate areas

Pop index 5: area=3*1=3
Pop index 4: area=2*4=8
Pop index 1: area=1*6=6

Why: Calculate areas for remaining bars considering full width

Result:

Largest rectangle area = 10

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func largestRectangleArea(heights []int) int {
	stack := []int{} // stack to store indices
	maxArea := 0
	for i := 0; i <= len(heights); i++ {
		var h int
		if i == len(heights) {
			h = 0 // sentinel to pop all remaining bars
		} else {
			h = heights[i]
		}
		for len(stack) > 0 && h < heights[stack[len(stack)-1]] {
			// pop the top
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			// calculate area with popped bar as smallest
			var width int
			if len(stack) == 0 {
				width = i
			} else {
				width = i - stack[len(stack)-1] - 1
			}
			area := heights[top] * width
			if area > maxArea {
				maxArea = area
			}
		}
		stack = append(stack, i) // push current index
	}
	return maxArea
}

func main() {
	heights := []int{2, 1, 5, 6, 2, 3}
	result := largestRectangleArea(heights)
	fmt.Println(result)
}

for i := 0; i <= len(heights); i++ {

iterate through all bars plus one extra to flush stack

if i == len(heights) { h = 0 } else { h = heights[i] }

use 0 height sentinel to pop all remaining bars at end

for len(stack) > 0 && h < heights[stack[len(stack)-1]] {

pop bars taller than current to calculate area

top := stack[len(stack)-1]; stack = stack[:len(stack)-1]

pop top index from stack

if len(stack) == 0 { width = i } else { width = i - stack[len(stack)-1] - 1 }

calculate width of rectangle using current and stack top indices

area := heights[top] * width; if area > maxArea { maxArea = area }

update max area if current area is larger

stack = append(stack, i)

push current index to stack

Output

10

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack storing indices in worst case

vs Alternative: Naive approach checks all pairs for max area with O(n^2) time, stack method is much faster

Edge Cases

empty histogram

returns 0 as no bars exist

DSA Go

for i := 0; i <= len(heights); i++ {

all bars same height

calculates area as height * number of bars

DSA Go

for len(stack) > 0 && h < heights[stack[len(stack)-1]] {

strictly increasing heights

stack grows until end, then popped by sentinel zero height

DSA Go

if i == len(heights) { h = 0 } else { h = heights[i] }

When to Use This Pattern

When asked for largest rectangle in histogram or largest area under curve, use stack to track increasing bars and calculate areas on height drops.

Common Mistakes

Mistake: Not adding a sentinel zero height at the end to pop all remaining bars
Fix: Add an extra iteration with height zero to flush stack and calculate all areas

Mistake: Calculating width incorrectly by not considering stack top after pop
Fix: Width = current index - stack top index - 1 if stack not empty, else current index

Summary

Finds the largest rectangle area in a histogram using a stack to track bars.

Use when you need to find max rectangle area efficiently in bar charts or histograms.

The key is to use a stack to keep bars in increasing order and calculate areas when a smaller bar appears.

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