LeetCode 221 - Maximal Square

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional binary matrix where each cell contains either '0' or '1'. Our task is to find the largest square submatrix that contains only '1' values, then return the area of that square.

The important detail is that we are looking specifically for a square, not just any rectangle. That means all sides must have equal length. If the largest valid square has side length k, then the answer is k * k.

For example, consider this matrix:

The largest square of only 1s has side length 2, so the returned area is 4.

The input size can be as large as 300 x 300, which means there can be up to 90,000 cells. This immediately suggests that extremely expensive approaches, especially ones that repeatedly scan large regions, may become too slow. An algorithm with cubic or quartic complexity would struggle at this scale.

There are several important edge cases to think about before designing the algorithm:

A matrix containing only 0s should return 0.
A matrix containing only 1s should return the entire matrix square area, if the matrix itself is square.
A single cell matrix must be handled correctly.
Rectangular matrices, where m != n, still require finding square regions.
Squares can appear anywhere in the matrix, not just near the top left corner.

The problem guarantees that the matrix dimensions are valid and every entry is either '0' or '1', so we do not need to validate the input format.

Approaches

Brute Force Approach

A straightforward approach is to treat every cell as the potential top left corner of a square. From each position, we try increasing square sizes and check whether every cell inside the square contains '1'.

For example, if we start at (row, col), we could try:

A 1 x 1 square
Then a 2 x 2 square
Then a 3 x 3 square
And so on until the square exceeds matrix boundaries

For every candidate square, we scan all cells inside it to verify that they are all '1'.

This approach is correct because it explicitly checks every possible square. However, it is very inefficient. For each starting position, we may examine many square sizes, and for each size we scan an entire square region.

In the worst case, this leads to roughly O(m * n * min(m,n)^3) complexity, which becomes too slow for matrices up to 300 x 300.

Dynamic Programming Insight

The key observation is that a square of side length greater than 1 can only exist if smaller squares already exist around it.

Suppose we want to determine the largest square ending at position (i, j).

If matrix[i][j] == '1', then the size of the square ending there depends on three neighboring positions:

Top cell (i-1, j)
Left cell (i, j-1)
Top left diagonal (i-1, j-1)

The current square can only grow if all three neighbors can also support squares.

Specifically:

dp[i][j] = 1 + min(
    dp[i-1][j],
    dp[i][j-1],
    dp[i-1][j-1]
)

This works because the smallest neighboring square limits how large the current square can become.

For example, if the top neighbor supports a square of size 3, the left supports 3, but the diagonal supports only 2, then the current cell can form at most a 3 x 3 square.

This transforms the problem into a dynamic programming problem with linear scanning of the matrix.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n * min(m,n)^3)	O(1)	Tries every possible square and validates all cells repeatedly
Optimal Dynamic Programming	O(m * n)	O(m * n)	Reuses previously computed square sizes

Algorithm Walkthrough

Create a DP table with the same dimensions as the matrix.

Each dp[i][j] represents the side length of the largest square whose bottom right corner is at (i, j). 2. Initialize a variable max_side to track the largest square side length found so far.

At the end, the answer will be max_side * max_side. 3. Iterate through every cell in the matrix row by row.

We process cells in row major order because each state depends only on previously computed neighbors. 4. If the current matrix cell contains '0', set dp[i][j] = 0.

A square cannot end at a cell containing 0. 5. If the current cell contains '1' and is in the first row or first column, set dp[i][j] = 1.

Any boundary cell can only form a square of side length 1 because there are no upper or left neighbors to expand from. 6. Otherwise, compute:

dp[i][j] = 1 + min(
    dp[i-1][j],
    dp[i][j-1],
    dp[i-1][j-1]
)

This determines the largest square that can extend to the current cell. 7. Update max_side whenever a larger square is found. 8. After processing the entire matrix, return max_side * max_side.

Why it works

The dynamic programming recurrence maintains the invariant that dp[i][j] always stores the largest valid square ending at (i, j).

A larger square can only exist if the top, left, and diagonal neighbors all support sufficiently large squares. Taking the minimum of those three values guarantees that every required cell inside the expanded square is valid. Adding 1 accounts for the current cell itself.

Because every state depends only on previously computed states, the algorithm correctly builds solutions from smaller subproblems to larger ones.

Python Solution

from typing import List

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

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

        for row in range(rows):
            for col in range(cols):
                if matrix[row][col] == "1":
                    if row == 0 or col == 0:
                        dp[row][col] = 1
                    else:
                        dp[row][col] = 1 + min(
                            dp[row - 1][col],
                            dp[row][col - 1],
                            dp[row - 1][col - 1]
                        )

                    max_side = max(max_side, dp[row][col])

        return max_side * max_side

The implementation begins by determining the matrix dimensions. We then allocate a DP table with matching dimensions, initialized to 0.

The nested loops process every matrix cell exactly once.

Whenever we encounter a '1', we determine the largest square ending at that position. Boundary cells are handled separately because they cannot expand from neighbors.

For all interior cells, the recurrence relation uses the minimum of the three neighboring DP values. This ensures the current square remains fully valid.

After updating the DP value, we compare it against max_side to track the largest square seen so far.

Finally, we return the square of the side length because the problem asks for area rather than side length.

Go Solution

func maximalSquare(matrix [][]byte) int {
	rows := len(matrix)
	cols := len(matrix[0])

	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	maxSide := 0

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if matrix[row][col] == '1' {
				if row == 0 || col == 0 {
					dp[row][col] = 1
				} else {
					dp[row][col] = 1 + min(
						dp[row-1][col],
						dp[row][col-1],
						dp[row-1][col-1],
					)
				}

				if dp[row][col] > maxSide {
					maxSide = dp[row][col]
				}
			}
		}
	}

	return maxSide * maxSide
}

func min(a, b, c int) int {
	smallest := a

	if b < smallest {
		smallest = b
	}

	if c < smallest {
		smallest = c
	}

	return smallest
}

The Go implementation closely mirrors the Python solution. The primary difference is explicit memory allocation for slices and the need for a helper min function because Go does not provide a built in minimum function for integers.

The matrix uses [][]byte, so comparisons are made against character literals like '1'.

Go arrays and slices are zero initialized automatically, so the DP table starts with all values set to 0.

Worked Examples

Example 1

Input:

We build the DP table step by step.

Initial DP table:

After processing row 0:

Cell	DP Value
(0,0)	1
(0,1)	0
(0,2)	1
(0,3)	0
(0,4)	0

DP state:

Processing row 1:

At (1,2):

1 + min(1,0,0) = 1

At (1,3):

1 + min(0,1,1) = 1

At (1,4):

1 + min(0,1,0) = 1

DP state:

Processing row 2:

At (2,2):

1 + min(1,1,0) = 1

At (2,3):

1 + min(1,1,1) = 2

At (2,4):

1 + min(1,2,1) = 2

DP state:

Processing row 3:

At (3,3):

1 + min(2,0,1) = 1

Final DP table:

The largest value is 2, so the answer is:

2 * 2 = 4

Example 2

Input:

0 1
1 0

DP table evolution:

Position	Value
(0,0)	0
(0,1)	1
(1,0)	1
(1,1)	0

Largest side length is 1.

Result:

Example 3

Input:

DP table:

No square of 1s exists.

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every cell is processed exactly once
Space	O(m * n)	The DP table stores one value per matrix cell

The algorithm scans the matrix a single time. Each DP state is computed in constant time using three neighboring values, so the total runtime is proportional to the number of cells.

The DP table requires storage for every matrix position, resulting in linear space relative to the matrix size.

Test Cases

solution = Solution()

assert solution.maximalSquare([
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
]) == 4  # Standard example with 2x2 square

assert solution.maximalSquare([
    ["0", "1"],
    ["1", "0"]
]) == 1  # Only single-cell squares exist

assert solution.maximalSquare([
    ["0"]
]) == 0  # Single zero cell

assert solution.maximalSquare([
    ["1"]
]) == 1  # Single one cell

assert solution.maximalSquare([
    ["1", "1"],
    ["1", "1"]
]) == 4  # Entire matrix forms a square

assert solution.maximalSquare([
    ["1", "1", "1"],
    ["1", "1", "1"]
]) == 4  # Rectangular matrix with largest 2x2 square

assert solution.maximalSquare([
    ["0", "0"],
    ["0", "0"]
]) == 0  # All zeros

assert solution.maximalSquare([
    ["1", "1", "1", "1"],
    ["1", "1", "1", "1"],
    ["1", "1", "1", "1"],
    ["1", "1", "1", "1"]
]) == 16  # Entire matrix is a 4x4 square

assert solution.maximalSquare([
    ["1", "0", "1", "1"],
    ["1", "1", "1", "1"],
    ["1", "1", "1", "0"]
]) == 4  # Largest square appears in the middle

assert solution.maximalSquare([
    ["1", "0", "1"],
    ["0", "1", "0"],
    ["1", "0", "1"]
]) == 1  # Diagonal ones do not form larger squares

Test	Why
Standard example matrix	Validates normal DP expansion
2x2 mixed matrix	Ensures isolated ones work correctly
Single zero cell	Smallest invalid case
Single one cell	Smallest valid case
Full 2x2 ones	Entire matrix forms a square
Rectangular matrix	Confirms non-square dimensions work
All zeros	Ensures algorithm returns 0
Full 4x4 ones	Tests maximum expansion behavior
Square in middle	Verifies internal square detection
Diagonal ones only	Prevents false square formation

Edge Cases

A matrix containing only 0s is an important edge case because no valid square exists. A careless implementation might incorrectly initialize the answer to 1 or fail to distinguish between valid and invalid cells. In this implementation, DP values remain 0 for every cell, so max_side never increases and the final answer correctly becomes 0.

Single row or single column matrices are another common source of bugs. Since the recurrence depends on upper and left neighbors, boundary handling must be correct. The implementation explicitly checks whether row == 0 or col == 0, ensuring these cells are treated as individual 1 x 1 squares when appropriate.

Matrices where almost all cells are 1 except for one blocking 0 can also expose logical errors. For example:

1 1 1
1 0 1
1 1 1

A naive approach might incorrectly assume a 3 x 3 square exists because many neighboring cells contain 1. The DP transition avoids this issue by taking the minimum of the three neighboring square sizes. The central 0 prevents larger square growth, so the algorithm correctly limits the maximum square size.