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);
}
Having problems with this solution? Click here to submit an issue on github.