Largest Rectangle in Histogram Using Stack in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Largest Rectangle Calculation

What is the output of the following Rust code that calculates the largest rectangle area in a histogram using a stack?

DSA Rust

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack = 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 as i32 } else { (i - stack.last().unwrap() - 1) as i32 };
            let area = heights[top] * width;
            if area > max_area {
                max_area = area;
            }
        }
    }
    while !stack.is_empty() {
        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;
        }
    }
    max_area
}

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

A 6

B 12

C 8

D 10

💡 Hint

Think about the largest rectangle that can be formed by consecutive bars in the histogram.

The largest rectangle area in the histogram [2, 1, 5, 6, 2, 3] is 10. This is formed by the bars with heights 5 and 6 (width 2), giving area 5*2=10.

🧠 Conceptual

intermediate

Understanding Stack Usage in Histogram Problem

Why do we use a stack to solve the Largest Rectangle in Histogram problem efficiently?

A To keep track of indices of bars in increasing height order for quick area calculation

B To count the total number of bars in the histogram

C To reverse the histogram for easier traversal

D To store the heights of bars in sorted order

💡 Hint

Think about how the stack helps find the width of rectangles quickly.

The stack stores indices of bars in increasing height order. When a smaller bar is found, it means the rectangle with the height of the bar at the top of the stack ends there. This helps calculate the area efficiently.

🔧 Debug

advanced

Identify the Error in Stack-Based Histogram Code

What error will the following Rust code produce when run?

DSA Rust

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack = Vec::new();
    let mut max_area = 0;
    let mut i = 0;
    while i <= heights.len() {
        let current_height = if i == heights.len() { 0 } else { heights[i] };
        if stack.is_empty() || current_height >= 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;
            }
        }
    }
    max_area
}

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

A No error, outputs 10 correctly

B Stack underflow panic when popping from empty stack

C Index out of bounds panic at heights[i]

D Infinite loop due to i never incrementing

💡 Hint

Check how the code handles the iteration beyond the last index.

The code uses a sentinel height 0 at the end by checking if i == heights.len(), so it safely processes all bars and empties the stack. It outputs 10 without error.

❓ Predict Output

advanced

Output of Modified Histogram with Equal Heights

What is the output of the Rust code calculating largest rectangle area for histogram [2, 2, 2, 2]?

DSA Rust

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack = 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 as i32 } else { (i - stack.last().unwrap() - 1) as i32 };
            let area = heights[top] * width;
            if area > max_area {
                max_area = area;
            }
        }
    }
    while !stack.is_empty() {
        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;
        }
    }
    max_area
}

fn main() {
    let histogram = vec![2, 2, 2, 2];
    println!("{}", largest_rectangle_area(histogram));
}

A 6

B 4

C 8

D 2

💡 Hint

All bars have the same height, so the largest rectangle covers all bars.

All bars have height 2 and there are 4 bars, so the largest rectangle area is 2 * 4 = 8.

🚀 Application

expert

Maximum Rectangle Area in a Binary Matrix Using Histogram Approach

Given a binary matrix, we convert each row into a histogram of heights of consecutive 1s and use the largest rectangle in histogram algorithm. For the matrix below, what is the maximum rectangle area of 1s? Matrix: [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

A 8

B 6

C 9

D 10

💡 Hint

Build histograms row by row and apply largest rectangle in histogram for each.

By building histograms for each row and applying the largest rectangle algorithm, the maximum rectangle area of 1s in the matrix is 6.

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