Maximal Rectangle in rust

The Challenge

link :https://leetcode.com/problems/maximal-rectangle

Given a binary matrix, we need to find the largest area of a rectangle consisting only of 1s.

Example Matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

In this case, the maximal rectangle has an area of 6.

The Core Insight: Histograms

Instead of looking at the matrix as a whole, imagine each row as the "ground" or the base of a histogram. For every row, we can calculate the height of consecutive 1s reaching up from that base.

1. Row 1: Heights are [1, 0, 1, 0, 0]

2. Row 2: Heights are [2, 0, 2, 1, 1] (Notice how we add to the previous row's height if the current cell is '1').

3. Row 3: Heights are [3, 1, 3, 2, 2]

By doing this, the problem transforms into: "Find the largest rectangle in a histogram," which we perform for every single row.

---

The Solution in Rust

We use a Monotonic Stack to solve the histogram sub-problem in linear time. This allows us to find the "left" and "right" boundaries for every bar where the bar itself is the shortest in that range.

Implementation

impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        if matrix.is_empty() || matrix[0].is_empty() { return 0; }

        let cols = matrix[0].len();
        let mut heights = vec![0; cols];
        let mut max_area = 0;

        for row in matrix {
            for j in 0..cols {
                // If we hit a '0', the height "resets" to the ground
                heights[j] = if row[j] == '1' { heights[j] + 1 } else { 0 };
            }
            // Update the global max using our histogram helper
            max_area = max_area.max(Self::largest_in_histogram(&heights));
        }

        max_area
    }

    fn largest_in_histogram(heights: &[i32]) -> i32 {
        let mut stack: Vec<usize> = Vec::new();
        let mut max_val = 0;
        let mut h_vec = heights.to_vec();
        h_vec.push(0); // Sentinel value to clear the stack at the end

        for (i, &current_h) in h_vec.iter().enumerate() {
            while let Some(&last_idx) = stack.last() {
                if current_h < h_vec[last_idx] {
                    stack.pop();
                    let h = h_vec[last_idx];
                    let w = if stack.is_empty() {
                        i as i32
                    } else {
                        (i - stack.last().unwrap() - 1) as i32
                    };
                    max_val = max_val.max(h * w);
                } else {
                    break;
                }
            }
            stack.push(i);
        }
        max_val
    }
}

---

Why This Works

1. Dynamic Programming for Heights

We don't re-calculate the heights from scratch for every row. We use the previous row's results ( update), which is a simple form of DP.

2. The Monotonic Stack Efficiency

The stack stores indices of bars in increasing order of height. When we encounter a bar shorter than the one at the top of the stack, we've found the right boundary for the rectangle. The element below the popped item in the stack is the left boundary.

Complexity Analysis

• Time Complexity: . We iterate through each cell once to update heights and once (effectively) during the stack operations.

• Space Complexity: , where is the number of columns, to store our heights array and the stack.

Conclusion

The Maximal Rectangle problem is a fantastic lesson in problem reduction. By recognizing that a 2D grid can be treated as a series of 1D histograms, we drop the complexity from a naive or down to a lean .

In Rust, the safety of the Vec and the clarity of the while let pattern make this algorithm both performant and readable.

---

Want to see more LeetCode solutions in Rust? Let me know in the comments which problem I should tackle next! 🦀