Maximal square

Array Dynamic Programming Matrix

50.0% acceptance

Jan 12, 2026

10976

260

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximal_square(matrix: Vec<Vec<char>>) -> i32 {
    if matrix.is_empty() { return 0; }
    let m = matrix.len();
    let n = matrix[0].len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    let mut max_side = 0;
    
    for i in 1..=m {
      for j in 1..=n {
        if matrix[i - 1][j - 1] == '1' {
          dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]) + 1;
          max_side = max_side.max(dp[i][j]);
        }
      }
    }
    max_side * max_side
  }
}