Maximal Square LeetCode 221 — 2D DP Guide

LeetCode 221 Maximal Square gives you an m x n binary matrix of characters '0' and '1'. Your task is to find the largest square submatrix containing only '1's and return its area. A square submatrix is defined by its bottom-right corner and its side length: a side-length-k square occupies rows [r-k+1, r] and columns [c-k+1, c]. All cells in this region must be '1' for it to count.

The output is the area of the largest such square — side length squared. If no '1' exists in the matrix, the answer is 0. This problem is a foundational 2D DP exercise because it introduces the elegant min-of-three-neighbors recurrence, which appears in several related matrix problems and is worth understanding deeply.

Understanding why the brute-force approach is slow and why the DP recurrence works requires thinking carefully about what information each cell needs to encode. The key question is: what is the right DP state definition that lets us extend smaller solutions to build larger ones?

The brute-force approach treats each cell (i, j) as the potential top-left corner of a square. For each such cell that contains '1', we try to expand a square outward: check if a 2x2 square fits, then 3x3, then 4x4, and so on, until we hit a '0' or a boundary. For each candidate side length k, we must verify that all k*k cells in the square are '1'. This verification takes O(k^2) time per cell per side length.

The total time complexity is O(m * n * min(m,n)^2). For an m x n matrix, there are O(m*n) cells, and for each cell we try up to min(m,n) side lengths, each requiring O(k^2) verification. On a 300x300 matrix, this is roughly 300 * 300 * 300^2 = 8.1 billion operations — far too slow. We need a smarter approach that reuses previous computations.

The key observation that leads to the DP solution is that checking whether a k x k square of '1's exists at (i,j) is related to checking whether (k-1) x (k-1) squares exist at (i-1,j), (i,j-1), and (i-1,j-1). If we precompute and cache these sub-results, we can answer each cell in O(1) instead of O(k^2).

Define dp[i][j] as the side length of the largest all-1 square whose bottom-right corner is at cell (i, j). If matrix[i][j] == '0', then dp[i][j] = 0 — no square can have its bottom-right corner here. If matrix[i][j] == '1', then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The base cases for the first row and first column are simply dp[i][j] = int(matrix[i][j]) since no 2x2 or larger square can fit with its corner at those edges.

The recurrence dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 works because a square of side k with bottom-right corner at (i,j) requires: a square of side k-1 ending at (i-1,j) (the cell above), a square of side k-1 ending at (i,j-1) (the cell to the left), and a square of side k-1 ending at (i-1,j-1) (the diagonal cell). If any one of these three sub-squares is smaller, the overall square cannot be of side k.

This definition makes the problem tractable. We traverse the matrix row by row, left to right, filling in dp values. The answer is the maximum dp value encountered, and the area is that maximum squared. The entire DP table can be computed in a single pass in O(m*n) time and O(m*n) space, with further optimization possible to reduce space to O(n).

The min-of-three-neighbors recurrence can be understood visually. Suppose dp[i-1][j] = 3, meaning there is a 3x3 all-1 square directly above cell (i,j), ending at row i-1. Suppose dp[i][j-1] = 2, meaning there is a 2x2 all-1 square to the left, ending at column j-1. And suppose dp[i-1][j-1] = 4, meaning there is a 4x4 all-1 square ending diagonally at (i-1,j-1). Can we form a 3x3 square ending at (i,j)?

The cell directly above (i-1,j) tells us how many rows of '1's are available going upward. The cell to the left (i,j-1) tells us how many columns of '1's are available going leftward. The diagonal cell (i-1,j-1) tells us the size of the square we can extend from the top-left. The bottleneck is the minimum of these three: even if two directions have plenty of '1's, the third constrains the maximum square we can form. A k x k square needs k consecutive '1's in all directions simultaneously.

In the example above, min(3, 2, 4) + 1 = 3, so dp[i][j] = 3. We can form a 3x3 square ending at (i,j). If any neighbor had been 0 (say dp[i][j-1] = 0), the min would be 0 and dp[i][j] = 1 — only a 1x1 square consisting of the current cell itself.

The full 2D DP table uses O(m*n) space. However, when computing row i, we only need values from row i-1 — the rest of the table is never accessed again. This means we can use a single 1D array of size n and overwrite it row by row. The tricky part is the diagonal: when we update dp[j] to the new value for (i,j), we overwrite the old dp[j] which was the value for (i-1,j). But we also need dp[i-1][j-1], which is the value dp[j-1] held before the current row started processing.

The fix is a single scalar variable prev that stores dp[i-1][j-1] — the diagonal value before overwriting. Before updating dp[j], save prev = dp[j] (the value about to be overwritten, which is dp[i-1][j]). After computing the new dp[j], update prev = old_dp[j] for the next iteration. This way, when computing dp[j+1] in the same row, prev correctly holds dp[i-1][j] (the diagonal for position j+1).

The space-optimized version runs in O(m*n) time and O(n) space. For a 300x300 grid, this reduces memory from 90,000 integers to 300 integers — a 300x improvement. While not always necessary for this problem size, the technique is important for larger grids and appears in other space-optimized DP problems like the knapsack variants.

Python O(m*n) space solution: def maximalSquare(matrix): m,n=len(matrix),len(matrix[0]); dp=[[0]*n for _ in range(m)]; maxSide=0; for i in range(m): for j in range(n): if matrix[i][j]=='1': dp[i][j]=1 if i==0 or j==0 else min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 maxSide=max(maxSide,dp[i][j]); return maxSide*maxSide. Python O(n) space: replace the 2D dp array with a 1D array and a prev variable tracking the diagonal.

Java O(m*n) solution: int maximalSquare(char[][] matrix) { int m=matrix.length, n=matrix[0].length, maxSide=0; int[][] dp=new int[m][n]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(matrix[i][j]=='1') { dp[i][j]=(i==0||j==0)?1:Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1; maxSide=Math.max(maxSide,dp[i][j]); } } return maxSide*maxSide; }. Java O(n) space: use a single int[] dp of length n with a prev variable for the diagonal.

Both solutions handle edge cases naturally: a matrix with all '0's returns 0 because maxSide stays 0. A 1x1 matrix with '1' returns 1 because dp[0][0]=1 and the area is 1*1=1. A matrix with all '1's returns min(m,n)^2. Always remember to square the side length for the final answer.

Maximal Rectangle (LeetCode 85) is the harder extension: given a binary matrix, find the largest rectangle (not necessarily square) containing only '1's. The standard approach uses the Largest Rectangle in Histogram (LeetCode 84) as a subroutine, treating each row as a histogram of column heights. Solving Maximal Square first builds the right intuition for thinking about 2D region problems, and the DP table from Maximal Square can even be reused as the height arrays for Maximal Rectangle.

Minimum Path Sum (LeetCode 64) and Search a 2D Matrix (LeetCode 74) are adjacent matrix problems. Minimum Path Sum uses a similar row-by-row DP where each cell depends on its top and left neighbors — the same neighborhood structure as Maximal Square. Search a 2D Matrix exploits the sorted property of the matrix for efficient binary search, showcasing a different algorithmic technique on the same data structure. Both are good practice after mastering Maximal Square.

The broader grid DP family includes problems like Unique Paths, Coin Change on a grid, and Dungeon Game. The unifying theme is that each cell's value depends on a small fixed neighborhood of previously computed cells, enabling a single-pass traversal. Maximal Square is an excellent entry point into this family because the min-of-three-neighbors recurrence is unusually clean and the state definition (side length at each corner) is an elegant encoding that directly captures the problem's structure.