LESSON 324 OF 414 · STACK

Largest Rectangle in Histogram in Rust: O(n) with a Monotonic Stack

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

The number of bars is between 1 and 10⁵
0 <= heights[i] <= 10⁴

STEP 1 OF 18

Guided

Ctrl + Enter to check

RUST · STACK

Largest Rectangle In Histogram in Rust, explained

Problem overview

The function largest_rectangle_area receives a vector heights. Each value is the height of one histogram bar, and every bar is 1 unit wide. The function returns the area of the largest rectangle that fits inside the histogram, with its sides along the bars and the axis.

For heights = [2, 1, 5, 6, 2, 3] the answer is 10: the bars of heights 5 and 6 are next to each other, and a rectangle of height 5 and width 2 has area 10. For [2, 4] the answer is 4, either the single bar of height 4 or the two bars together at height 2. The heights are between 0 and 10,000 and there can be up to 100,000 bars, so the answer is at most 1,000,000,000. That fits in an i32.

Approach: the lowest bar decides the height

Any rectangle in a histogram is limited by its shortest bar. So every candidate can be described by that shortest bar i: the rectangle has height heights[i] and stretches left and right for as long as the neighbouring bars are at least as tall. Trying every bar as the shortest one covers every possible best rectangle.

The brute-force version walks left and right from each bar to find how far it can stretch, which costs O(n) per bar and O(n²) overall. That is too slow for 100,000 bars. The faster idea finds both boundaries for all bars in linear time:

left[i] is the index of the nearest bar to the left of i that is lower than heights[i], or -1 if there is none.
right[i] is the index of the nearest lower bar to the right, or n if there is none.

The widest rectangle of height heights[i] covers the indices strictly between those two bars, so its width is right[i] - left[i] - 1 and its area is heights[i] * (right[i] - left[i] - 1).

Finding the nearest lower bar uses a stack of indices whose heights never decrease from bottom to top. A bar waits on the stack until a lower bar arrives. When bar i is lower than the bar on top, then i is the first lower bar that index has met, so its boundary is settled and it can be removed. Bars that were already on the stack and are taller get settled the same way, one after another, until the top is no taller than bar i. Then i joins the stack.

For [2, 1, 5, 6, 2, 3] the two passes give:

left  = [-1, -1, 1, 2, 1, 4]
right = [ 1,  6, 4, 4, 6, 6]

The areas are then 2, 6, 10, 6, 8 and 3, and the maximum is 10, from the bar of height 5 (indices 2 and 3 are inside its boundaries 1 and 4).

Step by step

Store the length as n. It is used for the loops and as the "no lower bar" marker.
Create left as a mutable vector of n values, all -1. The default means that no lower bar was found, as if a bar of height 0 stood just before the start.
Create right the same way, filled with n as i32, as if a zero-height bar stood just after the end.
Create the stack st as an empty Vec<usize>. It stores indices, so the element type is the one used for indexing.
Scan left to right and call the helper remove_and_update with right. When bar i arrives, every taller bar on the stack has found its nearest lower bar on the right.
Clear the stack. Whatever is still there has no lower bar to its right, and right already holds n for those. The second pass needs a fresh stack.
Scan right to left with (0..n).rev() and call the same helper with left. Going in the opposite direction, the first lower bar that an index meets is its nearest lower bar on the left.
Take the best area. Keep a running answer starting at 0, and for every bar compare it with the area computed from left and right.
Return answer as the last expression.
The helper pops while the stack is not empty and the current bar is strictly lower than the bar whose index is on top. Each popped index gets i stored in arr. Then it pushes i.

The solution in Rust

impl Solution {
    fn remove_and_update(heights: &[i32], st: &mut Vec<usize>, arr: &mut Vec<i32>, i: usize) {
        while !st.is_empty() && heights[i] < heights[*st.last().unwrap()] {
            let top = st.pop().unwrap();
            arr[top] = i as i32;
        }
        st.push(i);
    }

    fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let n = heights.len();
        let mut left = vec![-1i32; n];
        let mut right = vec![n as i32; n];
        let mut st: Vec<usize> = Vec::new();

        for i in 0..n {
            Self::remove_and_update(&heights, &mut st, &mut right, i);
        }

        st.clear();
        for i in (0..n).rev() {
            Self::remove_and_update(&heights, &mut st, &mut left, i);
        }

        let mut answer = 0i32;
        for i in 0..n {
            answer = answer.max(heights[i] * (right[i] - left[i] - 1));
        }
        answer
    }
}

Rust details worth a closer look:

Borrowing into the helper. &heights lends the vector read-only. The parameter type is the slice &[i32], and Rust converts &Vec<i32> to it automatically. &mut st and &mut right let the helper change the caller's vectors without taking ownership of them.
*st.last().unwrap(). last() returns an Option<&usize>. The unwrap() is safe because !st.is_empty() is checked first, and && stops evaluating as soon as that check fails. The * reads the index out of the reference so it can index heights.
Mixing usize and i32. Indices are usize, but left and right hold i32 values so that -1 is possible, and so that heights[i] * (right[i] - left[i] - 1) is plain i32 arithmetic. The conversions are n as i32 and i as i32.
(0..n).rev(). A loop counting down over a usize would have to stop at 0 without going to -1, which a usize can't hold. Reversing a range avoids the problem.
Final expression. answer has no semicolon, so it is the return value. answer.max(...) is the max method of i32, which returns the larger of the two values.

Complexity

Time: O(n). In each pass, every index is pushed once and popped at most once, so the while loops do at most n pops in total across the pass, even though a single call can pop many bars. Together with the final loop, that is about three linear passes.

Space: O(n). The vectors left and right hold n values each, and the stack holds up to n indices.

Edge cases and common mistakes

Equal heights. The helper pops only strictly taller bars. For [3, 3, 3] nothing is ever popped, so every bar gets the boundaries -1 and 3, a width of 3, and the answer is 9. If the condition were <=, each bar would stop at its equal neighbour, and the same input would return 3.
A single bar or zeros. [5] gives 5 and [0, 0, 0] gives 0. A zero-height bar produces area 0, and answer starts at 0.
Sorted heights. [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1] both give 9 (height 3 over three bars). In the increasing case nothing is popped in the left-to-right pass; in the right-to-left pass every new bar pops the one before it.
A dip in the middle. [2, 1, 2] gives 3: the bar of height 1 stretches over the whole histogram, which beats a single bar of height 2.
Forgetting clear(). Leftover indices from the first pass would be compared against the second pass, and they could overwrite correct values in left.
Overflow. The largest possible area is 100,000 × 10,000 = 1,000,000,000, below the i32 limit of about 2.1 billion. The lessons build with optimizations, where an overflow would wrap silently, so a wider type matters only if the limits grow.

Testing

[2, 1, 5, 6, 2, 3] gives 10.
[2, 4] gives 4.
[3, 3, 3] gives 9.
[2, 1, 2] gives 3.
[0] gives 0.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free