Maximal Square

How it works

The bottom-up DP only needs the current row and the next row to compute values. We can reduce space by using a single 1D array. As we process each row from right to left, we keep track of the previous diagonal value in a variable prev. This allows us to update the array in place while still having access to all three neighbors needed for the recurrence.

Steps

1. Create a 1D DP array of size n+1 initialized to 0.
2. Iterate from r = m-1 down to 0:
   • Set prev = 0 (represents the diagonal value from the previous iteration).
   • For each column c from n-1 down to 0:
     • Store dp[c] in temp (this will be the next diagonal).
     • If matrix[r][c] is '1', set dp[c] = 1 + min(dp[c], dp[c+1], prev) and update maxSquare.
     • Otherwise, set dp[c] = 0.
     • Update prev = temp.
3. Return maxSquare * maxSquare.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the number of rows and n is the number columns.

Things to watch for

Returning the Side Length Instead of the Area

The DP table stores the side length of the largest square, but the problem asks for the area. Forgetting to square the maximum side length before returning gives an incorrect answer.

Comparing Characters Instead of Character Values

Matrix elements are characters ('0' and '1'), not integers. Comparing against integer 0 or 1 instead of character '0' or '1' causes the condition to always evaluate incorrectly, resulting in wrong DP values.

Incorrect DP Recurrence Direction

The recurrence dp[r][c] = 1 + min(dp[r+1][c], dp[r][c+1], dp[r+1][c+1]) assumes processing from bottom-right to top-left. Processing in the wrong direction (top-left to bottom-right without adjusting the formula) references uncomputed values and produces incorrect results.

from typing import List

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        max_square = 0

        for r in range(m - 1, -1, -1):
            prev = 0
            for c in range(n - 1, -1, -1):
                temp = dp[c]
                if matrix[r][c] == "1":
                    dp[c] = 1 + min(dp[c], dp[c + 1], prev)
                    max_square = max(max_square, dp[c])
                else:
                    dp[c] = 0
                prev = temp

        return max_square * max_square

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(n + 1, 0);
        int maxSquare = 0;

        for (int r = m - 1; r >= 0; r--) {
            int prev = 0;
            for (int c = n - 1; c >= 0; c--) {
                int temp = dp[c];
                if (matrix[r][c] == '1') {
                    dp[c] = 1 + min({dp[c], dp[c + 1], prev});
                    maxSquare = max(maxSquare, dp[c]);
                } else {
                    dp[c] = 0;
                }
                prev = temp;
            }
        }

        return maxSquare * maxSquare;
    }
};