Largest Rectangle in Histogram Using Stack in DSA Rust

Mental Model

We use a stack to keep track of bars that are not yet processed for largest rectangle. When we find a bar shorter than the top of the stack, we calculate areas for bars taller than it.

Analogy: Imagine stacking books by height. When a shorter book arrives, you remove taller books from the stack to find the biggest flat surface you can make with those books.

Histogram bars: 2 1 5 6 2 3
Stack stores indices of bars in increasing height order.

Example:
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null
Stack: bottom [ ] top (stores indices)

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 -> null

Why: Start with first bar index to track increasing heights

Step 2: Current bar height 1 is less than height at stack top (2), pop index 0 and calculate area

Popped index 0 (height 2), stack empty
Calculate area: height 2 * width 1 = 2
Push index 1 (height 1)

Why: Found smaller bar, so calculate area for taller bars before pushing smaller

Step 3: Push index 2 (height 5) onto stack

Stack: [1, 2]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 5 is greater than height at stack top (1), so push

Step 4: Push index 3 (height 6) onto stack

Stack: [1, 2, 3]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 6 is greater than height at stack top (5), so push

Step 5: Current bar height 2 is less than height at stack top (6), pop index 3 and calculate area

Popped index 3 (height 6), stack: [1, 2]
Calculate area: height 6 * width 1 = 6

Why: Smaller bar found, calculate area for taller bar

Step 6: Current bar height 2 is less than height at stack top (5), pop index 2 and calculate area

Popped index 2 (height 5), stack: [1]
Calculate area: height 5 * width 2 = 10

Why: Continue popping taller bars to find max area

Step 7: Push index 4 (height 2) onto stack

Stack: [1, 4]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Push current smaller bar index after popping taller bars

Step 8: Push index 5 (height 3) onto stack

Stack: [1, 4, 5]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 3 is greater than height at stack top (2), so push

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

Pop index 5 (height 3), area = 3 * 1 = 3
Pop index 4 (height 2), area = 2 * 4 = 8
Pop index 1 (height 1), area = 1 * 6 = 6

Why: Calculate areas for remaining bars to find max rectangle

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let mut stack: Vec<usize> = Vec::new();
        let mut max_area = 0;
        let mut i = 0;
        let n = heights.len();

        while i < n {
            if stack.is_empty() || heights[i] >= heights[*stack.last().unwrap()] {
                stack.push(i);
                i += 1;
            } else {
                let top = stack.pop().unwrap();
                let width = if stack.is_empty() { i as i32 } else { (i - stack.last().unwrap() - 1) as i32 };
                let area = heights[top] * width;
                if area > max_area {
                    max_area = area;
                }
            }
        }

        while let Some(top) = stack.pop() {
            let width = if stack.is_empty() { n as i32 } else { (n - stack.last().unwrap() - 1) as i32 };
            let area = heights[top] * width;
            if area > max_area {
                max_area = area;
            }
        }

        max_area
    }
}

fn main() {
    let histogram = vec![2, 1, 5, 6, 2, 3];
    let result = Solution::largest_rectangle_area(histogram);
    println!("{}", result);
}

if stack.is_empty() || heights[i] >= heights[*stack.last().unwrap()] {

Push current index if stack empty or current height >= height at stack top

stack.push(i);

Add current bar index to stack to track increasing heights

i += 1;

Move to next bar

let top = stack.pop().unwrap();

Pop top index from stack to calculate area for taller bar

let width = if stack.is_empty() { i as i32 } else { (i - stack.last().unwrap() - 1) as i32 };

Calculate width of rectangle using current index and stack top

let area = heights[top] * width;

Calculate area with popped bar height and width

if area > max_area { max_area = area; }

Update max area if current area is larger

while let Some(top) = stack.pop() {

After processing all bars, pop remaining bars to calculate areas

Output

10

Complexity Analysis

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

Space: O(n) for the stack that stores indices of bars

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

Edge Cases

empty histogram

returns 0 as no bars exist

DSA Rust

while i < n { ... } with n = 0 means loop never runs

all bars same height

largest rectangle is height * number of bars

DSA Rust

if stack.is_empty() || heights[i] >= heights[*stack.last().unwrap()] { stack.push(i); }

strictly increasing heights

all bars pushed, then popped at end to calculate max area

DSA Rust

while let Some(top) = stack.pop() { ... }

When to Use This Pattern

When asked to find the largest rectangle in a histogram or similar problem, use a stack to track increasing heights and calculate areas when a smaller height appears.

Common Mistakes

Mistake: Not calculating width correctly when popping from stack
Fix: Use current index and stack top index to compute width as (i - stack.last() - 1) or i if stack empty

Mistake: Not popping remaining bars after processing all histogram bars
Fix: Add a final loop to pop all remaining bars and calculate areas

Summary

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

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

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

Practice

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

easy

A. To store the maximum area found so far

B. To sort the histogram bars by height

C. To reverse the order of histogram bars

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

Solution

1. Step 1: Understand stack usage in the problem

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

2. Step 2: Explain why this helps

   This allows quick calculation of largest rectangle areas when a smaller height bar is found.

3. Final Answer:

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

4. Quick Check:

   Stack tracks indices with increasing heights = C [OK]

Hint: Stack holds indices of increasing heights for area calculation [OK]

Common Mistakes:

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

2. Which of the following Rust code snippets correctly initializes an empty stack to store indices for the histogram bars?

easy

A. let mut stack: Vec<usize> = Vec::new();

B. let stack = Vec::with_capacity(0);

C. let stack: Vec<i32> = Vec::new();

D. let mut stack: Vec<i32> = Vec::new();

Solution

1. Step 1: Identify correct stack type for indices

   Indices are usize type, so stack must be Vec<usize>.

2. Step 2: Check mutability and initialization

   Stack must be mutable and initialized empty with Vec::new().

3. Final Answer:

   let mut stack: Vec<usize> = Vec::new(); -> Option A

4. Quick Check:

   Mutable Vec of usize initialized empty = B [OK]

Hint: Use mutable Vec<usize> for indices stack [OK]

Common Mistakes:

• Using wrong type like i32 for indices
• Not making stack mutable
• Using Vec::with_capacity(0) without mut

3. What is the output of the following Rust code that calculates the largest rectangle area in the histogram heights = [2, 1, 5, 6, 2, 3]?

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut max_area = 0;
    let mut i = 0;
    while i <= heights.len() {
        let h = if i == heights.len() { 0 } else { heights[i] };
        if stack.is_empty() || h >= heights[*stack.last().unwrap()] {
            stack.push(i);
            i += 1;
        } else {
            let top = stack.pop().unwrap();
            let width = if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 };
            max_area = max_area.max(heights[top] * width as i32);
        }
    }
    max_area
}

fn main() {
    println!("{}", largest_rectangle_area(vec![2, 1, 5, 6, 2, 3]));
}

medium

A. 12

B. 10

C. 9

D. 8

Solution

1. Step 1: Trace stack and area calculation

   For heights [2,1,5,6,2,3], largest rectangle area is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm max_area value

   Code correctly calculates max_area as 10 after processing all bars.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest rectangle area for example histogram is 10 [OK]

Common Mistakes:

• Confusing max area with sum of heights
• Miscomputing width when popping stack
• Forgetting to add sentinel zero height

4. Identify the bug in this Rust code snippet for Largest Rectangle in Histogram and select the fix:

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut max_area = 0;
    let mut i = 0;
    while i < heights.len() {
        if stack.is_empty() || heights[i] >= heights[*stack.last().unwrap()] {
            stack.push(i);
            i += 1;
        } else {
            let top = stack.pop().unwrap();
            let width = if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 };
            max_area = max_area.max(heights[top] * width as i32);
        }
    }
    max_area
}

medium

A. Subtract 1 from width calculation: i - stack.last().unwrap() - 1

B. Change while condition to i <= heights.len() and use 0 height sentinel

C. Make stack mutable by adding 'mut' keyword

D. Initialize max_area with i32::MIN instead of 0

Solution

1. Step 1: Identify width calculation error

   Width should be i - stack.last().unwrap() - 1 to exclude the popped bar's index.

2. Step 2: Explain fix impact

   Without subtracting 1, width is overcounted, causing wrong area calculation.

3. Final Answer:

   Subtract 1 from width calculation: i - stack.last().unwrap() - 1 -> Option A

4. Quick Check:

   Correct width calculation subtracts 1 [OK]

Hint: Width = i - previous index - 1 when popping stack [OK]

Common Mistakes:

• Missing -1 in width calculation
• Not handling sentinel zero height
• Incorrect while loop condition

5. Given a histogram with heights [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach? Explain how the stack helps find this area.

hard

A. 8

B. 10

C. 12

D. 15

Solution

1. Step 1: Use stack to track indices with increasing heights

   Push indices while heights increase; pop when current height is less to calculate areas.

2. Step 2: Calculate largest rectangle area

   Largest rectangle area is 12 (from bars at indices 2,3,4 with min height 4 and width 3).

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Stack helps find max area 12 [OK]

Hint: Stack finds max area 12 by tracking increasing heights [OK]

Common Mistakes:

• Calculating area without considering width correctly
• Ignoring bars after popping stack
• Not using sentinel zero height to flush stack