README.md

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'.

Solutions (Rust)

1. Solution

impl Solution {
    pub fn maximal_square(matrix: Vec<Vec<char>>) -> i32 {
        let mut matrix = matrix
            .iter()
            .map(|row| row.iter().map(|&c| c as i32 - 48).collect::<Vec<_>>())
            .collect::<Vec<_>>();
        let mut ret = 0;

        for i in 0..matrix.len() {
            for j in 0..matrix[0].len() {
                if matrix[i][j] == 1 && i > 0 && j > 0 {
                    matrix[i][j] += matrix[i - 1][j - 1]
                        .min(matrix[i][j - 1])
                        .min(matrix[i - 1][j]);
                }
                ret = ret.max(matrix[i][j]);
            }
        }

        ret * ret
    }
}