Largest Rectangle in Histogram Using Stack in DSA Rust - 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 larger

↓

Push current index to stack

↓

Repeat until all bars processed

↓

Pop remaining bars from stack and calculate area

↓

Return max area found

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 Rust

let heights = vec![2, 1, 5, 6, 2, 3];
let mut stack = Vec::new();
let mut max_area = 0;
for i in 0..=heights.len() {
    let current_height = if i == heights.len() { 0 } else { heights[i] };
    while !stack.is_empty() && current_height < heights[*stack.last().unwrap()] {
        let top = stack.pop().unwrap();
        let width = if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 };
        let area = heights[top] * width;
        if area > max_area {
            max_area = area;
        }
    }
    stack.push(i);
}
max_area

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	Stack (indexes)	Max Area	Visual State (Bars with stack top)
1	Start: stack empty	[]	0	Bars: 2 1 5 6 2 3
2	Push index 0 (height 2)	[0]	0	Stack top bar height 2
3	Current index 1 (height 1) < height at stack top (2)	[] after pop 0	2	Calculate area with height 2, width 1
4	Push index 1 (height 1)	[1]	2	Stack top bar height 1
5	Push index 2 (height 5)	[1,2]	2	Stack top bar height 5
6	Push index 3 (height 6)	[1,2,3]	2	Stack top bar height 6
7	Current index 4 (height 2) < height at stack top (6)	[1,2] after pop 3	6	Calculate area with height 6, width 1
8	Current index 4 (height 2) < height at stack top (5)	[1] after pop 2	10	Calculate area with height 5, width 2
9	Push index 4 (height 2)	[1,4]	10	Stack top bar height 2
10	Push index 5 (height 3)	[1,4,5]	10	Stack top bar height 3
11	End of array reached, pop remaining stack	[1,4] after pop 5	10	Calculate area with height 3, width 1
12	Pop index 4 (height 2)	[1] after pop 4	10	Calculate area with height 2, width 4
13	Pop index 1 (height 1)	[] after pop 1	10	Calculate area with height 1, width 6
14	Done	[]	10	Max area found is 10

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 11	After Step 14
stack	[]	[0]	[1]	[1,2,3]	[1,4]	[1,4]	[]
max_area	0	0	2	2	10	10	10
current_index	N/A	1	2	4	5	6 (end)	N/A

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 bars on the stack can't extend further right. We calculate area using popped bar as smallest height, as shown in steps 3, 7, and 8 in the execution_table.

Why do we push the current index after popping bars?

We push the current index to mark the start of a new potential rectangle with the current bar height. This keeps the stack in ascending order, as seen in steps 4, 9, and 10.

Why do we pop remaining bars after processing all histogram bars?

Remaining bars in stack mean they extend to the end of histogram. We calculate their areas considering width till the end, as in steps 11 to 13.

Visual Quiz - 3 Questions

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

A 6

B 10

C 12

D 2

💡 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 3

B Step 9

C Step 13

D Step 14

💡 Hint

Look at the 'Stack (indexes)' column to find when it changes to []

If the histogram heights were strictly increasing, how would the stack behave?

A Stack would always pop at each step

B Stack would remain empty

C Stack would keep growing with all indexes

D Stack would pop only at the end

💡 Hint

Refer to the concept_flow and how stack keeps indexes of ascending bars

Concept Snapshot

Largest Rectangle in Histogram Using Stack
- Use a stack to store indexes of bars in ascending height
- Iterate bars, pop stack when current bar is lower
- Calculate area with popped bar as smallest height
- Update max area during pops
- After iteration, pop remaining bars to calculate areas
- Return max area found

Full Transcript

This concept finds the largest rectangle area in a histogram using a stack. We scan bars left to right, pushing indexes of bars with increasing heights. When a lower bar appears, we pop from the stack and calculate areas using popped bars as the smallest height. This ensures we consider all possible rectangles. After processing all bars, we pop remaining bars to calculate their areas extending to the histogram end. The maximum area found during these steps is the answer. The stack helps track boundaries efficiently, avoiding repeated scanning. The execution table shows step-by-step stack changes, area calculations, and max area updates. Key moments clarify why and when we pop or push indexes. The visual quiz tests understanding of stack state and max area updates during execution.

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