Maximal Square (LeetCode 221)

The problem

You get a matrix of characters '0' and '1'. Find the largest square made entirely of '1's and return its area.

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

There is a 2×2 block of 1s at rows 1–2, columns 2–3 (and another at columns 3–4), so the area is 4. No 3×3 block exists.

How to think about it

Start with brute force. For every cell, treat it as a top-left corner and try growing a square one size at a time, checking each new row and column. That is roughly O((R·C)²) in the worst case.

The key insight: define the square by its bottom-right corner. Let dp[i][j] be the side of the largest all-1 square ending at (i, j). If the cell is '0', it’s 0. If it’s '1', the square can grow only as far as all three neighbours allow: the cell above, the cell to the left, and the diagonal up-left. So dp[i][j] = min(up, left, diag) + 1. If any of the three is short, the square is limited by it.

Why the minimum is exactly right. A square of side k ending at (i, j) contains squares of side k - 1 ending at each of those three neighbours. Conversely, if all three neighbours have squares of side at least k - 1, together with this cell they cover a full k × k square.

Which pattern is this? 2-D grid DP. The tell is “largest square of 1s”: each cell’s answer depends on three already-computed neighbours. The answer is the largest side seen, squared.

Approach

1. Keep one padded row dp of length C + 1 (so dp[0] is always 0) and best = 0.
2. For each row, reset prev (the diagonal) to 0. For each column j:
   • Save the old dp[j] in tmp; it’s the “up” value now and becomes the diagonal for the next column.
   • If the cell is '1', set dp[j] = min(dp[j], dp[j-1], prev) + 1 and update best. Otherwise set dp[j] = 0.
   • Set prev = tmp.
3. Return best * best.

Solution

def maximal_square(matrix):
    R, C = len(matrix), len(matrix[0]); dp = [0]*(C+1); best = 0; prev = 0
    for i in range(1, R+1):
        prev = 0                                  # diagonal for column 1
        for j in range(1, C+1):
            tmp = dp[j]                           # "up" now, "diagonal" for next column
            if matrix[i-1][j-1] == '1':
                dp[j] = min(dp[j], dp[j-1], prev) + 1; best = max(best, dp[j])   # up, left, diag
            else: dp[j] = 0
            prev = tmp
    return best * best
# maximal_square([["1","0","1","0","0"],["1","0","1","1","1"],
#                 ["1","1","1","1","1"],["1","0","0","1","0"]]) -> 4

Dry run

On the example, the dp row (without the padding cell) after each matrix row:

In row 3, column 4: up = 1, left = 1, diagonal = 1, so the side is 2. The best side is 2, so the area is 4.

Complexity

• Time: O(R · C). Each cell is visited once.
• Space: O(C). One padded row plus two temporaries.

Edge cases and pitfalls

• All '0' returns 0; a single '1' returns 1.
• The cells are strings. Comparing with the integer 1 instead of '1' makes every cell look like 0.
• Return the area, not the side. best * best.
• Rolling-row bug: forgetting to save the old dp[j] before overwriting loses the diagonal value for the next column.

Related problems

• Minimum Path Sum (LeetCode 64): another grid DP that combines up and left neighbours.
• Largest Rectangle in Histogram (LeetCode 84): the building block for the harder “maximal rectangle” variant.
• Number of Islands (LeetCode 200): a different way to reason about regions of 1s in a grid.