Maximal Square — Solution

Problem

Given a 2D matrix of '0's and '1's, find the area of the largest square submatrix that contains only '1's.

A counter-example: the matrix below has four '1's in a 2×2 block but any 3×3 region includes a '0', so the answer is still 4, not 9.

Intuition

At every '1' cell, ask: what is the largest all-'1' square whose bottom-right corner is exactly here? The answer depends only on three neighbors — directly above, directly to the left, and diagonally above-left. If each of those three neighbors can form a square of side at least s, you can form a square of side s+1 at the current cell. The minimum of the three constrains you — any single direction that falls short limits the current square.

Approach 1 — Brute Force

For each '1' cell as a potential top-left corner, expand the square one row and one column at a time, stopping as soon as any cell in the new border is '0'. Track the maximum valid side length seen.

1. For each cell (r, c) where matrix[r][c] == '1', record a potential square of side 1.
2. Try expanding to side 2, 3, ..., up to the remaining matrix bounds.
3. For each candidate expansion, check all cells in the new bottom row and new rightmost column.
4. If any cell is '0', stop expanding from this corner.
5. Update the global maximum side length after each valid expansion.
6. Return max_side².

1def maximalSquare(matrix: list[list[str]]) -> int:
2    rows, cols = len(matrix), len(matrix[0])
3    max_side = 0
4
5    for r in range(rows):
6        for c in range(cols):
7            if matrix[r][c] == '0':
8                continue
9            side = 1
10            max_side = max(max_side, 1)
11            # try expanding the square one row/column at a time
12            while r + side < rows and c + side < cols:
13                if any(matrix[r + side][c + k] == '0' for k in range(side + 1)):
14                    break
15                if any(matrix[r + k][c + side] == '0' for k in range(side + 1)):
16                    break
17                side += 1
18                max_side = max(max_side, side)
19
20    return max_side * max_side

Time: O(mn · min(m,n)²) — O(mn) starting cells, each expanded up to min(m,n) times, with O(min(m,n)) cell checks per expansion step. Space: O(1) — no auxiliary data structure beyond a few scalar variables.

Approach 2 — Dynamic Programming

Build a table where dp[i][j] stores the side length of the largest all-'1' square with its bottom-right corner at (i, j). Each cell's value follows from three already-computed neighbors, so a single left-to-right, top-to-bottom pass suffices.

1. Initialize a dp table of the same dimensions, filled with 0s.
2. For each cell (i, j): if matrix[i][j] == '0', leave dp[i][j] = 0.
3. For cells on the first row or first column, set dp[i][j] = 1 (they can form at most a 1×1 square).
4. Otherwise: dp[i][j] = min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]) + 1.
5. Track the maximum dp value seen throughout; return max_side².

1def maximalSquare(matrix: list[list[str]]) -> int:
2    rows, cols = len(matrix), len(matrix[0])
3    dp = [[0] * cols for _ in range(rows)]
4    max_side = 0
5
6    for i in range(rows):
7        for j in range(cols):
8            if matrix[i][j] == '0':
9                continue
10            if i == 0 or j == 0:
11                dp[i][j] = 1  # border cells can only form a 1×1 square
12            else:
13                # constrained by the shortest reach in any of the three neighboring directions
14                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
15            max_side = max(max_side, dp[i][j])
16
17    return max_side * max_side

Time: O(mn) — a single pass through all m×n cells. Space: O(mn) — the dp table; reducible to O(n) with a rolling single-row array since each row only reads from the row immediately above it.

Complexity Summary

Common Mistakes

• Confusing dp[i][j] for area instead of side length. The recurrence operates on side lengths. Track the max side length, then square once at the end — not per cell.
• Omitting the diagonal neighbor. Using only min(dp[i-1][j], dp[i][j-1]) + 1 without dp[i-1][j-1] will falsely extend across a '0' hidden diagonally. All three neighbors are required.
• Skipping the border row/column special case. When i == 0 or j == 0, the recurrence would read out-of-bounds indices. Border cells can form at most a 1×1 square, which the special case sets directly.
• Returning max_side instead of max_side². The problem asks for area, not side length. The variable name dp[i][j] makes it tempting to return it directly.
• Trying to adapt this recurrence to Maximal Rectangle. The min(three neighbors) + 1 formula is specific to squares. Maximal Rectangle requires a different technique — maintaining a heights histogram and applying Largest Rectangle in Histogram per row.

Related Problems

• maximal-rectangle — extends the square problem to arbitrary rectangles; requires a histogram-based stack approach instead of this DP
• largest-rectangle-in-histogram — the key subproblem underpinning Maximal Rectangle, contrasting with this DP
• unique-paths — same 2D DP traversal pattern where each cell depends on two previously computed neighbors
• minimum-path-sum — grid DP with a similar top-left to bottom-right cell dependency structure
• 01-matrix — 2D grid problem where BFS propagates values outward, showing an alternative approach to grid-based distance problems