13 Jun 2025•PHP•Medium

Maximal Square

find the largest square of 1s in a binary matrix using dynamic programming.

View original LeetCode question

dp[i][j] represents the side length of the largest square ending at (i,j). if matrix[i][j] is 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

the min ensures we only extend squares that can form a valid larger square. track the maximum side length seen during the dp process.

dp state

dp[i][j] = largest square side ending at (i,j). depends on top, left, and top-left neighbors. only extend if all three allow it.

complexity

O(mn) time and space where m and n are matrix dimensions. can be optimized to O(n) space by using only previous row.

Solution files

PHP•maximal-square/solution.php
<?php

class Solution
{
    public function maximalSquare($matrix)
    {
        if (empty($matrix) || empty($matrix[class="syntax-number">0])) {
            return class="syntax-number">0;
        }

        $rows = count($matrix);
        $cols = count($matrix[class="syntax-number">0]);
        $dp = array_fill(class="syntax-number">0, $cols, class="syntax-number">0);
        $best = class="syntax-number">0;

        for ($r = class="syntax-number">0; $r < $rows; $r++) {
            $prevDiagonal = class="syntax-number">0;
            for ($c = class="syntax-number">0; $c < $cols; $c++) {
                $temp = $dp[$c];

                if ($matrix[$r][$c] === class="syntax-string">'class="syntax-number">1') {
                    $left = $c > class="syntax-number">0 ? $dp[$c - class="syntax-number">1] : class="syntax-number">0;
                    $dp[$c] = min($left, $dp[$c], $prevDiagonal) + class="syntax-number">1;
                    if ($dp[$c] > $best) {
                        $best = $dp[$c];
                    }
                } else {
                    $dp[$c] = class="syntax-number">0;
                }

                $prevDiagonal = $temp;
            }
        }

        return $best * $best;
    }
}