Largest Rectangle in Histogram Using Stack in DSA Go - Deep Dive

Overview - Largest Rectangle in Histogram Using Stack

What is it?

The Largest Rectangle in Histogram problem asks us to find the biggest rectangle that can fit inside a histogram made of bars of different heights. Each bar has a width of 1 unit. We want to find the area of the largest rectangle that can be formed by one or more consecutive bars. This problem helps us understand how to use stacks to solve range and area problems efficiently.

Why it matters

Without this method, finding the largest rectangle would require checking every possible rectangle, which takes a long time for many bars. Using a stack speeds up the process, making it practical for real-world tasks like image processing, stock analysis, or layout design. Without this, programs would be slower and less efficient when handling similar problems.

Where it fits

Before this, you should know basic arrays and stacks, and how to use them. After learning this, you can explore more complex range queries, like maximum area in 2D matrices or advanced stack problems.

Mental Model

Core Idea

Use a stack to keep track of bars in increasing height order so that when a shorter bar appears, you can calculate the largest rectangle possible with the taller bars before it.

Think of it like...

Imagine stacking books by height on a shelf from shortest to tallest. When you find a shorter book, you remove taller books one by one to see how wide a stack you can make with each book before the shorter one stops you.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]

Stack stores indices of bars with increasing heights:

Start: stack = []
Push index 0 (height 2): stack = [0]
Push index 1 (height 1): height 1 < height 2, so pop 0 and calculate area

Diagram:

Index: 0   1   2   3   4   5
Height: 2 | 1 | 5 | 6 | 2 | 3
Stack:  ┌────┐
        │ 1  │  <- top
        └────┘

When a bar is shorter, pop from stack and calculate area:
Area = height_of_popped_bar * width_between_current_and_stack_top

Repeat until stack is empty or current bar taller than top of stack.

Build-Up - 7 Steps

1

Foundation

Understanding Histogram and Rectangle Area

Concept: Learn what a histogram is and how to calculate the area of rectangles formed by bars.

A histogram is a set of bars placed side by side. Each bar has a height and a width of 1 unit. The area of a rectangle formed by consecutive bars is the height of the shortest bar times the number of bars. For example, bars with heights [2, 1, 5] can form rectangles like: - Single bar 2: area = 2 * 1 = 2 - Bars 2 and 1: area = 1 * 2 = 2 (shortest bar is 1) - Bars 1, 5: area = 1 * 2 = 2 - Bars 2, 1, 5: area = 1 * 3 = 3 We want to find the largest such area.

Result

You understand how to calculate rectangle areas in a histogram by multiplying the shortest bar height by the width (number of bars).

Knowing how area depends on the shortest bar helps us realize why we need to track bar heights carefully to find the largest rectangle.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is a collection where you add items on top (push) and remove the top item (pop). It follows Last-In-First-Out (LIFO) order. For example, if you push 1, then 2, then 3, popping will remove 3 first, then 2, then 1. Stacks help keep track of items in order and are useful for problems where you need to remember previous states.

Result

You can use a stack to store and retrieve items in reverse order of insertion.

Understanding stack behavior is key because the largest rectangle algorithm uses a stack to remember bars in increasing height order.

3

Intermediate

Using Stack to Track Increasing Bar Heights

🤔Before reading on: do you think the stack should store bar heights or their indices? Commit to your answer.

Concept: Store indices of bars in the stack to efficiently calculate widths when popping bars.

Instead of storing bar heights, we store their indices in the stack. This helps us calculate the width of rectangles when we pop bars. We keep pushing indices of bars as long as their heights increase. When we find a bar shorter than the top of the stack, we pop bars and calculate areas using the popped bar's height and the distance between current index and the new top of the stack.

Result

Stack contains indices of bars in increasing height order, allowing quick area calculation when a shorter bar appears.

Storing indices rather than heights lets us find the width of rectangles without extra loops, making the algorithm efficient.

4

Intermediate

Calculating Area When Popping Bars

🤔Before reading on: when popping a bar, should the width be from the current index or from the next index after the new stack top? Commit to your answer.

Concept: Calculate width as the distance between current index and the index after the new top of the stack after popping.

When popping a bar at index 'top', the width of the rectangle with height bars[top] is: - If stack is empty after popping, width = current index - Else, width = current index - stack top index - 1 This width covers all bars between the new top and the current index, where the popped bar is the shortest.

Result

You can calculate the largest rectangle area for each popped bar correctly using stack indices.

Knowing how to calculate width precisely avoids off-by-one errors and ensures correct area calculation.

5

Intermediate

Handling Remaining Bars After Iteration

Concept: After processing all bars, pop remaining bars from the stack to calculate areas.

Once we finish iterating through all bars, some bars remain in the stack. These bars have increasing heights and extend to the end of the histogram. We pop each remaining bar and calculate area using the total length of the histogram as the right boundary. This ensures we consider rectangles that extend to the histogram's end.

Result

All possible rectangles are considered, including those ending at the last bar.

Handling leftover bars ensures no potential largest rectangle is missed.

6

Advanced

Complete Go Implementation with Stack

🤔Before reading on: do you think the algorithm runs in O(n) or O(n^2) time? Commit to your answer.

Concept: Implement the largest rectangle algorithm in Go using a stack for O(n) time complexity.

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 bars } else { h = heights[i] } for len(stack) > 0 && h < heights[stack[len(stack)-1]] { top := 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 := heights[top] * width if area > maxArea { maxArea = area } } stack = append(stack, i) } return maxArea } func main() { histogram := []int{2, 1, 5, 6, 2, 3} fmt.Println(largestRectangleArea(histogram)) }

Result

Output: 10 Explanation: The largest rectangle has area 10, formed by bars with heights 5 and 6 (width 2).

Implementing the algorithm shows how the stack and sentinel value work together to achieve linear time complexity.

7

Expert

Why Stack Approach is O(n) and Not O(n²)

🤔Quick: Does each bar get pushed and popped multiple times or only once? Commit to your answer.

Concept: Each bar is pushed and popped at most once, making the algorithm linear time.

The key to O(n) time is that each bar's index is pushed onto the stack once and popped once. The inner while loop pops bars only when a shorter bar is found, but since bars are never pushed back, total operations are proportional to the number of bars. This avoids the nested loop behavior of naive solutions.

Result

The algorithm runs efficiently even for large histograms.

Understanding the push-pop frequency clarifies why the stack method is optimal and avoids hidden quadratic costs.

Under the Hood

The stack keeps indices of bars in increasing height order. When a new bar is shorter, it triggers popping taller bars from the stack. Each popped bar's area is calculated using its height and the width between the current index and the new stack top. This process ensures all maximal rectangles ending before the current bar are considered. The sentinel bar of height 0 at the end forces all remaining bars to be popped and processed.

Why designed this way?

The stack approach was designed to avoid checking all possible rectangles explicitly, which is slow. By remembering only increasing bars, the algorithm quickly finds boundaries where rectangles can extend. Alternatives like brute force check every pair of bars, leading to O(n²) time, which is impractical for large inputs.

Input bars: [2, 1, 5, 6, 2, 3]

Stack process:

Start: stack = []

Push 0 (height 2): stack = [0]
Push 1 (height 1): height 1 < 2, pop 0
Calculate area with height 2, width 1
stack = []
Push 1: stack = [1]
Push 2 (height 5): stack = [1, 2]
Push 3 (height 6): stack = [1, 2, 3]
Push 4 (height 2): height 2 < 6, pop 3
Calculate area with height 6, width 1
height 2 < 5, pop 2
Calculate area with height 5, width 2
stack = [1]
Push 4: stack = [1, 4]
Push 5 (height 3): stack = [1, 4, 5]

End: push sentinel 0
Pop 5, 4, 1 calculating areas

Stack visualization:

┌─────┐
│  1  │ <- bottom (height 1)
│  4  │
│  5  │ <- top (height 3)
└─────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the stack store bar heights or their indices? Commit to your answer.

Common Belief: The stack stores the heights of bars directly.

Reality: The stack stores indices of bars, not their heights, to calculate widths efficiently.

Why it matters: Storing heights instead of indices makes it impossible to calculate the width of rectangles correctly, leading to wrong area calculations.

Quick: Is the algorithm's time complexity O(n²) because of nested loops? Commit to your answer.

Common Belief: Because of the nested while loop inside the for loop, the algorithm runs in O(n²) time.

Reality: Each bar is pushed and popped at most once, so the total operations are O(n), making the algorithm linear time.

Why it matters: Misunderstanding time complexity may discourage using this efficient method for large inputs.

Quick: After finishing the main loop, can we ignore remaining bars in the stack? Commit to your answer.

Common Belief: Once the main loop ends, remaining bars in the stack do not affect the result and can be ignored.

Reality: Remaining bars must be popped and processed to consider rectangles extending to the histogram's end.

Why it matters: Ignoring leftover bars causes missing the largest rectangle, leading to incorrect answers.

Expert Zone

1

The sentinel bar of height 0 at the end is a clever trick to flush out all remaining bars without extra code.

2

The algorithm can be adapted to find largest rectangle in binary matrices by applying it row-wise.

3

Stack-based approach can be modified to track not only area but also the exact rectangle boundaries (start and end indices).

When NOT to use

This stack method is ideal for 1D histograms. For 2D histograms or irregular shapes, other algorithms like segment trees or divide-and-conquer may be better. Also, if bars have varying widths, this method needs adjustment or different approaches.

Production Patterns

Used in image processing to find largest rectangular areas in pixel histograms, in financial software to analyze stock price ranges, and in UI layout engines to optimize space usage.

Connections

Monotonic Stack

Builds-on

Largest Rectangle in Histogram is a classic example of using a monotonic stack, which maintains elements in sorted order to solve range problems efficiently.

Maximum Area Rectangle in Binary Matrix

Builds-on

By treating each row of a binary matrix as a histogram, the largest rectangle algorithm can be applied repeatedly to find the maximum rectangle of 1s.

Stock Span Problem

Similar pattern

Both problems use stacks to find previous smaller or larger elements, showing how stack-based range queries solve different real-world problems.

Common Pitfalls

#1 Pushing bar heights instead of indices onto the stack.

Wrong approach:

stack := []int{}
for i, h := range heights {
for len(stack) > 0 && h < stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
stack = append(stack, h)
}

Correct approach:

stack := []int{}
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]] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// calculate area
}
stack = append(stack, i)
}

Root cause:

Confusing what data is needed to calculate widths leads to storing wrong values in the stack.

#2 Not processing remaining bars after the main loop ends.

Wrong approach:

for i := 0; i < len(heights); i++ {
// process bars
}
// no code to pop remaining bars

Correct approach:

for i := 0; i <= len(heights); i++ {
// process bars including sentinel
}

Root cause:

Forgetting that some bars extend to the histogram's end causes missing largest rectangles.

#3 Calculating width incorrectly when stack is empty after popping.

Wrong approach:

width := i - stack[len(stack)-1]

Correct approach:

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

Root cause:

Not handling empty stack case leads to wrong width and area calculations.

Key Takeaways

The largest rectangle in histogram problem finds the biggest rectangle area formed by consecutive bars in a histogram.

Using a stack to store indices of bars in increasing height order allows efficient calculation of rectangle areas.

Each bar is pushed and popped at most once, making the algorithm run in linear time O(n).

A sentinel bar of height zero at the end ensures all bars are processed correctly.

Careful width calculation using stack indices is crucial to avoid off-by-one errors and get the correct largest area.

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