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

class Solution {
    /**
     * @param String[][] $matrix
     * @return Integer
     */
    public function maximalSquare($matrix) {
        $m = count($matrix);
        if ($m == 0) {
            return 0;
        }
        $n = count($matrix[0]);
        if ($n == 0) {
            return 0;
        }
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        $max = 0;
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($matrix[$i][$j] == '1') {
                    $next = 1 + min($dp[$i][$j], min($dp[$i + 1][$j], $dp[$i][$j + 1]));
                    if ($next > $max) {
                        $max = $next;
                    }
                    $dp[$i + 1][$j + 1] = $next;
                }
            }
        }
        return $max * $max;
    }
}

This site is open source. Improve this page.