LeetCode 221: Maximal Square

A clear explanation of finding the largest square of 1s in a binary matrix using dynamic programming.

leetcodedynamic-programmingmatrix

Problem Restatement

We are given an m x n binary matrix.

Each cell contains either:

"0"
"1"

We need to find the largest square that contains only "1" cells.

Return the area of that square.

The official statement says: given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

Input and Output

Item Meaning
Input Binary matrix of strings "0" and "1"
Output Area of the largest square of only 1s
Shape required Square, not rectangle
Area side_length * side_length

Example function shape:

def maximalSquare(matrix: list[list[str]]) -> int:
    ...

Examples

Example 1:

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"],
]

The largest square of 1s has side length 2.

So its area is:

2 * 2 = 4

Answer:

4

Example 2:

matrix = [
    ["0","1"],
    ["1","0"],
]

The largest square has side length 1.

Answer:

1

Example 3:

matrix = [["0"]]

There is no square of 1s.

Answer:

0

First Thought: Check Every Square

A direct way is:

  1. Pick every cell as the top-left corner.
  2. Try every possible square size from that cell.
  3. Check whether all cells in the square are "1".
  4. Track the largest valid square.

This works, but it repeats a lot of checks.

For a large matrix, repeatedly scanning square areas becomes too slow.

Key Insight

Instead of asking:

What is the largest square starting here?

we ask:

What is the largest square ending here?

More precisely:

dp[r][c] = side length of the largest all-1 square
           whose bottom-right corner is at cell (r, c)

If matrix[r][c] == "0", then no all-1 square can end there:

dp[r][c] = 0

If matrix[r][c] == "1", then the square ending there depends on three neighbors:

Neighbor Meaning
Top Largest square ending above
Left Largest square ending left
Top-left Largest square ending diagonally

The current cell can extend a square only if all three directions support it.

So:

dp[r][c] = 1 + min(top, left, top_left)

Why the Minimum Matters

Suppose the current cell is "1".

To form a square of side length s ending at this cell, we need:

  • a square of side s - 1 above
  • a square of side s - 1 to the left
  • a square of side s - 1 diagonally above-left

The weakest of these three limits the new square.

For example, if the top supports side 3, the left supports side 3, but the diagonal supports only side 1, then the current square can only become side 2.

That is why we use the minimum.

Algorithm

  1. Create a DP table with one extra row and one extra column of zeros.
  2. Track max_side.
  3. For each matrix cell:
    • If the cell is "1":
      • compute the side length using top, left, and top-left
      • update max_side
    • If the cell is "0":
      • leave the DP value as 0
  4. Return max_side * max_side.

The extra row and column avoid boundary checks.

Walkthrough

Use a smaller matrix:

matrix = [
    ["1","0","1"],
    ["1","1","1"],
    ["1","1","0"],
]

We use a padded DP table.

After processing, the DP values for the original cells are:

1 0 1
1 1 1
1 2 0

At cell (2, 1), the value is 2.

That means the largest square ending there has side length 2.

The square is:

1 1
1 1

The maximum side length is 2.

Return:

2 * 2 = 4

Correctness

The algorithm defines dp[r][c] as the side length of the largest all-1 square whose bottom-right corner is at (r, c).

If matrix[r][c] == "0", no square of 1s can end at that cell, so the correct value is 0.

If matrix[r][c] == "1", any square ending there must also have valid all-1 squares touching its top, left, and top-left regions. The largest possible square is limited by the smallest of those three neighboring square sizes. Adding the current cell extends that smallest common support by one.

Therefore the recurrence computes the correct largest square ending at each cell.

The algorithm checks every possible bottom-right corner. The largest square in the whole matrix must have some bottom-right corner, so tracking the maximum DP value finds its side length.

Returning the square of that side length gives the required area.

Complexity

Metric Value Why
Time O(m * n) Each matrix cell is processed once
Space O(m * n) Full DP table

Where m is the number of rows and n is the number of columns.

Implementation

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        max_side = 0

        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                if matrix[r - 1][c - 1] == "1":
                    dp[r][c] = 1 + min(
                        dp[r - 1][c],
                        dp[r][c - 1],
                        dp[r - 1][c - 1],
                    )
                    max_side = max(max_side, dp[r][c])

        return max_side * max_side

Code Explanation

Get the matrix dimensions:

rows = len(matrix)
cols = len(matrix[0])

Create a padded DP table:

dp = [[0] * (cols + 1) for _ in range(rows + 1)]

The padding means dp[r - 1][c], dp[r][c - 1], and dp[r - 1][c - 1] are always valid.

Track the largest side length:

max_side = 0

Process every original matrix cell using shifted DP indices:

for r in range(1, rows + 1):
    for c in range(1, cols + 1):

If the current cell is "1":

if matrix[r - 1][c - 1] == "1":

compute the largest square ending here:

dp[r][c] = 1 + min(
    dp[r - 1][c],
    dp[r][c - 1],
    dp[r - 1][c - 1],
)

Update the best side length:

max_side = max(max_side, dp[r][c])

Return area:

return max_side * max_side

Space-Optimized Implementation

We only need the previous row and the current row.

So we can reduce space to O(n).

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        dp = [0] * (cols + 1)
        max_side = 0
        prev_diag = 0

        for r in range(1, rows + 1):
            prev_diag = 0

            for c in range(1, cols + 1):
                top = dp[c]

                if matrix[r - 1][c - 1] == "1":
                    dp[c] = 1 + min(
                        dp[c],
                        dp[c - 1],
                        prev_diag,
                    )
                    max_side = max(max_side, dp[c])
                else:
                    dp[c] = 0

                prev_diag = top

        return max_side * max_side

Here:

Variable Meaning
dp[c] before update Top neighbor
dp[c - 1] Left neighbor
prev_diag Top-left neighbor

Testing

def run_tests():
    s = Solution()

    matrix = [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"],
    ]
    assert s.maximalSquare(matrix) == 4

    assert s.maximalSquare([["0","1"],["1","0"]]) == 1
    assert s.maximalSquare([["0"]]) == 0
    assert s.maximalSquare([["1"]]) == 1
    assert s.maximalSquare([["1","1"],["1","1"]]) == 4
    assert s.maximalSquare([["1","1","1"],["1","1","1"]]) == 4

    print("all tests passed")

run_tests()
Test Why
Standard matrix Finds side length 2
Diagonal ones Only side length 1
Single zero No square
Single one Area 1
2 x 2 all ones Full matrix square
2 x 3 all ones Largest square side is 2