Largest Rectangle in Histogram Using Stack in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to find the largest rectangle in a histogram?

Use a stack to keep track of bars in increasing height order. When a smaller bar appears, calculate areas with bars popped from the stack as heights, using current index to find width.

beginner

Why do we push indices of bars instead of their heights onto the stack?

Indices help calculate the width of rectangles when popping bars. Heights alone don't give position info needed for width calculation.

intermediate

In the stack-based algorithm, what triggers the calculation of rectangle areas?

When the current bar's height is less than the height of the bar at the top of the stack, we pop from the stack and calculate area for the popped bar.

intermediate

What is the time complexity of the largest rectangle in histogram algorithm using a stack?

O(n), because each bar is pushed and popped at most once from the stack.

advanced

Explain how the width of the rectangle is calculated when popping a bar from the stack.

Width = current index - index of new top of stack - 1. If stack is empty after popping, width = current index.

What data structure is used to solve the largest rectangle in histogram problem efficiently?

A Queue

B Stack

C Linked List

D Hash Map

A stack is used to keep track of bars in increasing order to calculate areas efficiently.

When do we pop bars from the stack during the algorithm?

A When current bar height is less than top of stack

B When current bar height equals top of stack

C When current bar height is greater than top of stack

D At the end only

We pop bars when the current bar is shorter, to calculate areas for taller bars.

What does the stack store in this algorithm?

A Bar heights

B Bar widths

C Bar indices

D Bar colors

Stack stores indices to calculate widths of rectangles.

What is the time complexity of the stack-based largest rectangle algorithm?

A O(n^2)

B O(n log n)

C O(log n)

D O(n)

Each bar is pushed and popped once, so time complexity is O(n).

If the stack is empty after popping a bar, how is the width calculated?

A Width = current index

B Width = 1

C Width = 0

D Width = index of popped bar

If stack is empty, width is the current index because the rectangle extends from start.

Describe step-by-step how the stack helps find the largest rectangle in a histogram.

Think about how the stack keeps track of bars and when areas are calculated.

Explain how to calculate the width of the rectangle when popping a bar from the stack.

Width depends on positions stored in the stack.

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