LeetCode-in-All

221. Maximal Square

Medium

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

Solution

impl Solution {
    pub fn maximal_square(matrix: Vec<Vec<char>>) -> i32 {
        let m = matrix.len();
        if m == 0 {
            return 0;
        }
        let n = matrix[0].len();
        if n == 0 {
            return 0;
        }

        // Create a 2D dp vector initialized to 0
        let mut dp = vec![vec![0; n + 1]; m + 1];
        let mut max_side = 0;

        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == '1' {
                    // Calculate the size of the square ending at (i, j)
                    dp[i + 1][j + 1] = 1 + dp[i][j].min(dp[i + 1][j]).min(dp[i][j + 1]);
                    max_side = max_side.max(dp[i + 1][j + 1]);
                }
            }
        }

        // Return the area of the largest square
        (max_side * max_side) as i32
    }
}

This site is open source. Improve this page.