LeetCode 221: Maximal Square

Solutions to LeetCode problems of Medium or higher difficulty often require a key insight. Even once you understand the problem and the general technique required to solve it, there’s no way to implement an efficient solution without it. Fortunately, dynamic programming gives us heuristics that we can use to point towards the required idea. For LeetCode 221: Maximal Square, the key insight requires some geometric intuition. But once you figure that part out, the rest of the problem is straightforward.

The input for Maximal Square is a 2D char array, where each cell contains the character '0' or the character '1' (not the integers 0 and 1). The goal is to find the largest square containing only the character '1', and return its area.

Using our standard approach for dynamic programming problems, we can start with a dp array of the same dimensions as the input array, where each dp[i][j] stores the best solution at that position — maybe the area of the largest square with a corner at (i, j).

As usual with DP solutions, we need to find an approach where combining smaller subproblems gets us the solution to a larger subproblem, and eventually the original problem. For example, consider the area of the largest square with a top left corner at (0, 0). Since we have our memo table dp, we can assume that we know the area of the largest nearby squares. How can we use that information?

To answer this question, we need to realize that:

• If a cell is 0, it can’t be the corner of a square.

• If a cell is 1, it might complete a square by filling in the last corner cell. More specifically, if the 1 cell is surrounded by squares whose sides are at least length s, then we can use it to make a square with side length s+1.

This implies that each element in our dp array needs to store the length of a side, not the area of a square. If we fill our dp array row by row from the top left to the bottom right of the input array, then we only need to check three adjacent cells: the cell to the right (East), the cell below (South), and the cell diagonally to the right and down (Southeast). The remaining adjacent cells will have already been checked in previous steps.

This can be tricky to visualize, so I recommend looking at the excellent diagrams by arkaung on LeetCode.

These two rules form the basis of our recursive function. If we want a function maxSide(i, j) to return the side length of the largest square with its top left corner at (i, j), then:

• If (i, j) is '0', return 0, since (i, j) can’t be part of a square.

• Otherwise, return 1 + min(maxSide(i+1, j), maxSide(i+1, j+1), maxSide(i, j+1)). This works because we can make a square side one larger than the smallest adjacent side. (See the References section below for a diagram illustrating that rule).

Once we add memoization to avoid repeatedly calculating the length at the same position, we’re done with the maxSide function.

In the main function, we’ll call maxSide for each position in the input matrix, keeping track of the maximum side length. That will give us the best top left corner starting position. Then we can return maxSide * maxSide to calculate the area of the square with that corner.

Pseudocode

matrix = input char array of size m x n containing '0' and '1' values
dp = int array of size m x n

max = 0
for i from 0 to m-1
    for j from 0 to n-1
        max = max(max, maxSide(i, j))

return max * max

function maxSide(int i, int j)
    if i or j are out of bounds, return 0
    if matrix[i][j] == '0', return 0

    if dp[i][j] > 0
        return dp[i][j]

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

    return dp[i][j]

Optimizations

Optimization 1: As usual, since we only need information about adjacent cells, we can save space by only storing the adjacent row and column rather than the full dp array.

Optimization 2: To avoid the overhead of recursive function calls, we can use a bottom-up approach. If we do that, the adjacent cells we’ll look at will be above, left, and above-left compared to the current cell. We’ll use these cells because, in the bottom-up approach, we need to look back at dp values that we have previously calculated.

References

For a few bottom-up implementations, see Jianchao Li solution on LeetCode.

Here’s another good visual explanation of the key step, showing why we need to use the minimum side length.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.