221. Maximal Square

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.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

Rust Solution

struct Solution;

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

#[test]
fn test() {
    let matrix = vec_vec_char![
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ];
    assert_eq!(Solution::maximal_square(matrix), 4);
}