Maximal Square: DP on a Binary Matrix
You are given an m x n binary matrix filled with 0s and 1s. Find the largest square containing only 1s and return its area.
This is LeetCode 221: Maximal Square, and it is one of the cleanest examples of 2D DP on a matrix. Unlike Maximal Rectangle, which reduces the problem to a histogram stack, the maximal square problem has a compact DP recurrence that you can memorize and reproduce in minutes.
Why this problem matters
Maximal Square teaches you how to define a DP state that represents "the largest valid structure ending at this cell." That same idea appears in longest common subsequence, edit distance, and dozens of other 2D DP problems. The recurrence is short, the logic is visual, and the space optimization is clean. It is a perfect problem for building DP fluency on a binary matrix.
The brute force
The naive approach checks every possible square in the matrix. For each cell, try it as the top-left corner of a square of increasing size. Verify every cell inside is a 1. This takes O(m * n * min(m, n)^2) time in the worst case. For a 300x300 matrix, that is painfully slow.
There is a much better approach. Instead of checking squares from the outside, you build up square sizes from the inside using DP.
The key insight: if you know the largest square ending at the three neighbors of a cell (top, left, top-left diagonal), you can compute the largest square ending at the current cell in O(1).
The DP recurrence
Define dp[i][j] as the side length of the largest square whose bottom-right corner is at (i, j).
If matrix[i][j] == '0', then dp[i][j] = 0. No square can end at a zero.
If matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
The answer is max(dp[i][j])^2 across all cells.
Why the min of three neighbors works
This is the part that trips people up. Why the minimum? Think of it as a bottleneck.
For a k x k square to end at (i, j), three things must all be true:
- There is a
(k-1) x (k-1)square ending at(i-1, j)(the cell above). This covers the top portion. - There is a
(k-1) x (k-1)square ending at(i, j-1)(the cell to the left). This covers the left portion. - There is a
(k-1) x (k-1)square ending at(i-1, j-1)(the diagonal). This covers the top-left interior.
If any of these three is smaller than k-1, you cannot form a k x k square. The weakest neighbor limits the result. That is why you take the min and add 1.
Think of it like building a wall from three overlapping foundations. The wall can only be as tall as the shortest foundation allows.
Walking through the DP table
Let's trace the algorithm on our example matrix. Watch how the three neighbors determine each cell's value.
Step 1: Base case. First row and first column copy directly from the matrix.
If a cell is in the first row or first column, dp[i][j] = matrix[i][j]. A single cell is a 1x1 square at best.
Step 2: dp[1][2]. matrix[1][2] = 1, so dp = min(top, left, diagonal) + 1 = min(1, 0, 0) + 1 = 1.
The left neighbor is 0, so the best square ending here is only 1x1. The min of three neighbors is the bottleneck.
Step 3: dp[2][3]. matrix[2][3] = 1, so dp = min(1, 1, 1) + 1 = 2. A 2x2 square ends here.
All three neighbors are 1, so min is 1. Adding 1 gives dp = 2. Global max so far: 2.
Step 4: dp[3][4]. matrix[3][4] = 1, so dp = min(2, 2, 2) + 1 = 3. A 3x3 square ends here!
All three neighbors are 2. min(2, 2, 2) + 1 = 3. Global max updates to 3. The answer is 3^2 = 9.
Step 5: Final DP table. The largest value is 3, so the maximal square has area 9.
dp[3][4] = 3 is the global maximum. The answer is 3 * 3 = 9.
The global maximum in the DP table is 3, found at dp[3][4]. The answer is 3 * 3 = 9.
The Python solution
def maximalSquare(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == "1":
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
Clean, no tricks. The entire logic is the min(top, left, diagonal) + 1 line. Everything else is setup.
Space optimization to O(n)
Look at the recurrence. Each cell depends on three neighbors: directly above, directly left, and diagonally above-left. When processing row i, you only need row i-1. That means you can compress the 2D table into a single row.
The catch is that when you overwrite dp[j], you lose the old value, which is the "above" value for the next column. You also need the old dp[j-1] as the diagonal. So you save it in a variable before overwriting.
def maximalSquare(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [0] * n
max_side = 0
prev = 0
for i in range(m):
for j in range(n):
temp = dp[j]
if matrix[i][j] == "1":
if i == 0 or j == 0:
dp[j] = 1
else:
dp[j] = min(dp[j], dp[j-1], prev) + 1
max_side = max(max_side, dp[j])
else:
dp[j] = 0
prev = temp
return max_side * max_side
Same O(m * n) time, but now O(n) space instead of O(m * n).
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (check every square) | O(m * n * min(m,n)^2) | O(1) |
| 2D DP table | O(m * n) | O(m * n) |
| 1D DP (space optimized) | O(m * n) | O(n) |
The DP solution visits every cell once and does O(1) work per cell. The space-optimized version keeps a single row of length n. You cannot do better than O(m * n) time because you must read every cell at least once.
Edge cases
- All zeros: every
dp[i][j]stays 0. Return 0. - All ones: dp values grow from 1 in the top-left corner toward min(m, n) at the bottom-right. Return
min(m, n)^2. - Single row: no cell has a "top" neighbor. Every
1producesdp[i][j] = 1. Return 1 if any cell is1, else 0. - Single column: same logic. No cell has a "left" neighbor.
- 1x1 matrix: return the value of the single cell.
The building blocks
Maximal Square is built on one core pattern: 2D DP with neighbor dependencies. You define a table where each cell depends on a small fixed set of neighboring cells, fill row by row, and track a global optimum.
The same pattern shows up in:
- Unique Paths (LeetCode 62): each cell sums the cell above and the cell to the left. Different recurrence, same fill order.
- Maximal Rectangle (LeetCode 85): a harder variant that finds rectangles instead of squares. Uses histogram stacks rather than the simple min-of-three recurrence.
- Min Path Sum (LeetCode 64):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Same two-neighbor dependency. - Edit Distance (LeetCode 72): three-neighbor dependency (top, left, diagonal), just like Maximal Square.
The difference between these problems is the recurrence, not the structure. Once you can set up a 2D DP table, define the base cases, and fill it in order, you have the building block for all of them.
From understanding to recall
Reading through this solution, the recurrence makes sense. min(top, left, diagonal) + 1. The bottleneck principle clicks. But knowing the idea and producing it under pressure are different skills.
In an interview, you need to remember that the DP state is "side length of the largest square ending at this corner," write the three-neighbor min recurrence without hesitation, handle the base cases for the first row and column, and track the global max. That takes practice, not just understanding.
Spaced repetition closes the gap. You revisit this problem at increasing intervals, writing the solution from scratch each time. After a few reps, the pattern becomes automatic. You see a binary matrix problem and your hands know what to write.
The 2D neighbor-dependency DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding problems at random.
Related posts
- Maximal Rectangle - The harder variant that finds rectangles instead of squares, using histogram stacks
- Unique Paths - The simplest 2D grid DP, teaching the same row-by-row fill pattern