Chapter 21: DP on a Matrix - Maximal Square

We've used dynamic programming on 2D grids to solve pathfinding problems ("Unique Paths", "Minimum Path Sum"). Now, we'll use a similar grid structure to solve a different kind of problem: finding the largest possible subsquare of a certain type. This introduces a powerful way to define our state.

LeetCode's "Maximal Square" (Problem #221) is the quintessential problem for this pattern. The solution is elegant and relies on a simple but brilliant observation about how squares are formed.

The Problem:

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

For example:

• Matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

• Output: 4

• Explanation: The largest square of 1s has a side length of 2, so its area is 4.

The Key Insight: The DP State

The crucial idea is how to define dp[i][j]. Instead of representing the answer for the whole grid up to (i, j), we'll define it more locally:

dp[i][j] = The side length of the largest square of 1s whose bottom-right corner is at cell (i, j).

With this definition, the solution to the overall problem will be the square of the maximum value we find anywhere in our dp table.

The State Transition

How do we calculate the side length for a square ending at (i, j)?

1. If matrix[i][j] is '0', then no square can end at this cell. The side length is 0.

2. If matrix[i][j] is '1', a square of at least side 1 can end here. To have a square of side s > 1, the cells at (i-1, j), (i, j-1), and (i-1, j-1) must also support a square. Specifically, they must be the bottom-right corners of squares of at least side s-1. This means the new side length is limited by the smallest of the squares ending at those three locations.

   side_length(i, j) = 1 + min(side_length(i-1, j), side_length(i, j-1), side_length(i-1, j-1))

This recursive relationship is the core of the solution.

Approach 1: Recursive Solution (Top-Down)

A pure recursive solution defines a function solve(i, j) that computes the side length of the largest square ending at (i, j). We must call this function for every cell and track the maximum value found.

from typing import List

def maximalSquare_recursive(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    max_side = 0

    def solve(r, c):
        # Base case: out of bounds
        if r < 0 or c < 0:
            return 0

        if matrix[r][c] == '0':
            return 0

        # Recursive step
        top = solve(r - 1, c)
        left = solve(r, c - 1)
        diag = solve(r - 1, c - 1)

        return 1 + min(top, left, diag)

    for r in range(rows):
        for c in range(cols):
            max_side = max(max_side, solve(r, c))

    return max_side * max_side

# This is extremely inefficient due to massive re-computation of subproblems.

Approach 2: Memoization (Top-Down DP)

We can easily optimize the recursion by caching the result for each (r, c) pair.

import functools
from typing import List

class Solution:
    def maximalSquare_memoized(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        max_side = 0

        @functools.lru_cache(maxsize=None)
        def solve(r, c):
            if r < 0 or c < 0:
                return 0

            if matrix[r][c] == '0':
                return 0

            # This ensures subproblems are solved before being used
            # but it is not necessary for the min calculation itself.
            solve(r-1, c)
            solve(r, c-1)
            solve(r-1, c-1)

            return 1 + min(solve(r - 1, c), solve(r, c - 1), solve(r - 1, c - 1))

        for r in range(rows):
            for c in range(cols):
                max_side = max(max_side, solve(r, c))

        return max_side * max_side

# solver = Solution()
# matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
# print(solver.maximalSquare_memoized(matrix)) # 4

Approach 3: Iteration (Bottom-Up DP)

For this problem, the iterative approach is the most straightforward. We build a dp table that directly maps to our dp[i][j] state definition.

1. Create a dp table of size (rows + 1) x (cols + 1) and initialize with zeros. This padding simplifies boundary checks.

2. Initialize a max_side variable to 0.

3. Iterate through the matrix, from i = 1 to rows and j = 1 to cols.

4. If matrix[i-1][j-1] is '1', calculate dp[i][j] using the min of its three neighbors in the dp table.

5. Update max_side = max(max_side, dp[i][j]).

6. The final answer is max_side * max_side.

def maximalSquare_iterative(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0

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

    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            if matrix[i-1][j-1] == '1':
                # The state transition
                dp[i][j] = 1 + min(dp[i-1][j],      # Top
                                   dp[i][j-1],      # Left
                                   dp[i-1][j-1])    # Diagonal
                max_side = max(max_side, dp[i][j])

    return max_side * max_side

Space Optimization

Notice that calculating dp[i][j] only requires values from the previous row (i-1) and the current row (i). We can optimize the space complexity from O(m*n) down to O(n) by only storing one row at a time.

def maximalSquare_optimized(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1) # Represents the previous row
    max_side = 0
    prev_diag = 0 # Stores the top-left (diagonal) value

    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            temp = dp[j] # Store dp[i-1][j] before it's overwritten
            if matrix[i-1][j-1] == '1':
                # dp[j-1] is dp[i][j-1] from current row
                # dp[j] is dp[i-1][j] from previous row
                # prev_diag is dp[i-1][j-1]
                dp[j] = 1 + min(dp[j], dp[j-1], prev_diag)
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev_diag = temp

    return max_side * max_side

Conclusion

"Maximal Square" is a fantastic problem that introduces a new perspective on grid-based DP. The key takeaway is the state definition: dp[i][j] as the solution to a subproblem ending at (i, j). This powerful technique is applicable to many other problems where you need to find optimal shapes or subarrays. The logic of how the solution at (i, j) is constrained by its neighbors is fundamental to this entire class of problems, and seeing it evolve from a slow recursion to a space-optimized iteration builds a complete mental model of the solution.