Maximal rectangle

Array Dynamic Programming Stack Matrix Monotonic Stack

58.1% acceptance

Jan 12, 2026

12021

226

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
    if matrix.is_empty() {
      return 0;
    }
    
    let m = matrix.len();
    let n = matrix[0].len();
    let mut heights = vec![0; n];
    let mut max_area = 0;
    
    for i in 0..m {
      for j in 0..n {
        if matrix[i][j] == '1' {
          heights[j] += 1;
        } else {
          heights[j] = 0;
        }
      }
      max_area = max_area.max(Self::largest_rect_85(&heights));
    }
    
    max_area
  }
  
  fn largest_rect_85(heights: &[i32]) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut max_area = 0;
    let mut heights = heights.to_vec();
    heights.push(0);
    
    for i in 0..heights.len() {
      while !stack.is_empty() && heights[*stack.last().unwrap()] > heights[i] {
        let h_idx = stack.pop().unwrap();
        let h = heights[h_idx];
        let w = if stack.is_empty() {
          i
        } else {
          i - stack.last().unwrap() - 1
        };
        max_area = max_area.max(h * w as i32);
      }
      stack.push(i);
    }
    
    max_area
  }
}