221. Maximal Square

Time: O(m x n)

Space: O(m x n)

Intuition

dp[i][j] = side length of the largest square whose bottom-right corner is (i,j). If matrix[i][j]=="1": dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The bottleneck is the smallest of the three neighbors. Track max dp value and return max^2.

Algorithm

1dp[i][j] = 0 if matrix[i][j]=="0".
2If i==0 or j==0: dp[i][j] = matrix[i][j]-"0".
3Else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
4Track maxSide. Return maxSide^2.

Example Walkthrough

Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

1.dp[2][3]: min(dp[1][3]=1, dp[2][2]=1, dp[1][2]=1)+1=2.
2.dp[2][4]: min(dp[1][4]=1, dp[2][3]=2, dp[1][3]=1)+1=2.
3.maxSide=2, answer=4.

Output: 4

Common Pitfalls

•The min of THREE neighbors (not two) - you need all three to be >= k for a k*k square to form.

221.cs

// Approach: Define dp[i][j] as the side length of the largest all-'1' square with its bottom-right corner at (i,j).
// Recurrence: if matrix[i][j] == '1', dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
// The minimum of the three neighbors limits the square size — the weakest neighbor is the bottleneck.
// If matrix[i][j] == '0', dp[i][j] = 0 since no square can have its corner here.
// Track the maximum dp value seen; the area is (maxSide)^2.
// The dp table can be compressed to a 1D rolling array to reduce space to O(n).
// Time: O(m x n) Space: O(m x n); reducible to O(n) with a rolling array.

public class Solution
{
    public int MaximalSquare(char[][] matrix)
    {
        int m = matrix.Length;
        int n = matrix[0].Length;
        int maxi = 0;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n];
            dp[i][0] = matrix[i][0] - '0';
        }

        for (int j = 0; j < n; j++)
            dp[0][j] = matrix[0][j] - '0';

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (matrix[i][j] == '1')
                    dp[i][j] = 1 + Math.Min(dp[i - 1][j], Math.Min(dp[i - 1][j - 1], dp[i][j - 1]));
                else
                    dp[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
                maxi = Math.Max(maxi, dp[i][j]);
        }

        return maxi * maxi;
    }
}

Was this solution helpful?