176. Maximal Square

Let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner is (i,j). A cell can extend a square only as far as its top, left, and top-left neighbors all allow — so dp[i][j] = 1 + min of those three (when the cell is '1').

Idea

Define dp[i][j] = the side of the biggest all-1 square ending (bottom-right) at cell (i, j). If matrix[i][j] is '1', that square can only be as large as its three neighbors (top, left, top-left) simultaneously permit — the smallest of them plus one:

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

If the cell is '0', dp[i][j] = 0. Track the maximum side; the answer is its square.

Algorithm

1. Use a (m+1) x (n+1) dp grid (extra row/col of zeros avoids bounds checks).
2. For each 1 cell, apply the recurrence and update best.
3. Return best * best.

Worked example

In the sample matrix the largest all-ones square has side 2, so the area is 2 * 2 = 4.

Complexity

• Time: O(m·n).
• Space: O(m·n) (reducible to O(n)).

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int best = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    best = Math.max(best, dp[i][j]);
                }
            }
        }
        return best * best;
    }
}