Largest Rectangle in Histogram Using Stack in DSA Rust - Build from Scratch

Largest Rectangle in Histogram Using Stack

📖 Scenario: You are working with a histogram, which is like a bar chart showing heights of bars side by side. Each bar has a certain height, and you want to find the largest rectangle that can fit inside the histogram.Imagine you have a row of boxes of different heights lined up. You want to find the biggest rectangle you can make by choosing some consecutive boxes.

🎯 Goal: Build a Rust program that finds the largest rectangle area in a histogram using a stack. You will create the histogram data, set up a stack to help find the largest rectangle, write the logic to calculate the area, and finally print the largest area found.

📋 What You'll Learn

Create a vector called heights with the exact values: [2, 1, 5, 6, 2, 3]

Create a mutable vector called stack to store indices of bars

Write a loop to iterate over the bars and use the stack to calculate the largest rectangle area

Print the largest rectangle area as an integer

💡 Why This Matters

🌍 Real World

Finding the largest rectangle in a histogram is useful in image processing, stock market analysis, and land area calculations where you want to find the biggest continuous area under a curve or bars.

💼 Career

This problem teaches stack usage and efficient area calculation, which are important in software engineering roles involving algorithms, data analysis, and performance optimization.

1

Create the histogram data

Create a vector called heights with these exact values: [2, 1, 5, 6, 2, 3]

DSA Rust

# Create the histogram heights vector
# Your code here

Hint

Use let heights = vec![2, 1, 5, 6, 2, 3]; to create the vector.

2

Set up the stack and variables

Add a mutable vector called stack to store indices of bars and a variable max_area set to 0 to keep track of the largest area.

DSA Rust

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    // Create a mutable vector called stack to store indices
    // Create a variable max_area and set it to 0
    // Your code here
}

Hint

Use let mut stack: Vec = Vec::new(); and let mut max_area = 0;.

3

Calculate the largest rectangle area using the stack

Write a for loop with variable i from 0 to heights.len() inclusive. Inside the loop, use a while loop to pop from stack while the current height is less than the height at the top of the stack. Calculate the area for each popped bar and update max_area. After the loop, process remaining bars in stack similarly.

DSA Rust

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    let mut stack: Vec = Vec::new();
    let mut max_area = 0;

    // Loop through all bars including one extra iteration
    // Use while loop to pop from stack and calculate area
    // Update max_area accordingly
    // After loop, process remaining bars in stack
    // Your code here
}

Hint

Use a loop from 0 to heights.len() inclusive. Use a while loop to pop from stack while current height is less than height at stack top. Calculate area as height * width and update max_area.

4

Print the largest rectangle area

Write a println! statement to print the value of max_area.

DSA Rust

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    let mut stack: Vec = 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 let Some(&top) = stack.last() {
            if current_height  max_area {
                    max_area = area;
                }
            } else {
                break;
            }
        }
        stack.push(i);
    }

    // Print the largest rectangle area
    // Your code here
}

Hint

Use println!("{}", max_area); to print the largest area.

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