Maximal square

Find the largest square made only of 1s in a binary matrix. Each cell asks its three neighbours how big a square they end, and grows the smallest by one.

The idea

Let dp[i, j] be the side of the biggest all-1 square whose bottom-right corner is cell (i, j). A square of side k ending here needs squares of side k - 1 ending directly above, directly to the left and diagonally up-left; the smallest of those three is the limit. So dp = 1 + min(up, left, up-left) on a 1, and 0 on a 0. The answer is the largest dp value, squared.

Code

public int MaximalSquare(char[][] matrix) {
    int rows = matrix.Length, cols = matrix[0].Length, best = 0;
    var dp = new int[rows + 1, cols + 1]; // extra 0 row and column: every cell has up, left and up-left
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++) {
            if (matrix[i - 1][j - 1] == '0') continue; // no square can end on a 0: dp stays 0
            dp[i, j] = 1 + Math.Min(dp[i - 1, j], Math.Min(dp[i, j - 1], dp[i - 1, j - 1]));
            best = Math.Max(best, dp[i, j]);
        }
    return best * best; // dp holds side lengths; the area is the side squared
}

Tips

• It is the minimum, not the maximum: one short neighbour leaves a gap in the square. Watch cell (1, 1) in the default example: left and up-left are 1, but above it is a 0, so it stays 1.
• The padded zero row and column remove every edge case: cells on the top row or left column simply see 0s outside the matrix.
• Only the previous row is ever read, so a 1D array of cols + 1 values plus one saved "up-left" value cuts the space to O(cols).

In the .NET library

new int[rows + 1, cols + 1] is a rectangular array that the runtime fills with zeros, so the padding row and column cost no extra code. Index it as dp[i, j] (one bracket pair) rather than dp[i][j].