Matrix DP & BFS

Maximal Square

Find the largest square of 1s. dp[i][j] = side length of largest square with bottom-right corner at (i,j). If cell is 1: dp[i][j] = 1 + min(top, left, top-left). The min is the bottleneck, all three must support the square.

O(m*n)

say this out loud

The square ending at a cell is limited by its three neighbours, so I take their minimum plus one. That single recurrence is the whole solution.

How It Works

Define dp[i][j] as the side length of the largest all-ones square whose bottom-right corner sits at cell (i, j). If the cell holds a 0, dp[i][j] is 0. If it holds a 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]): the square can only extend as far as the weakest of the squares ending above, to the left, and diagonally up-left. The answer is the maximum dp value seen, squared for area.

The min is the heart of the recurrence, all three neighboring squares must be large enough to support a bigger one, so the smallest is the bottleneck. Checking every possible square by brute force costs O(m*n*min(m,n)^2), while the DP is a single O(m*n) pass. Row-by-row filling means only the previous row is needed, compressing space to O(n).

Step-by-Step Visualization

Find the largest square of 1s in this 3 by 5 grid

best side0

1/8

Code

Java

static int maximalSquare(char[][] matrix) {
  int m = matrix.length, n = matrix[0].length;
  int[][] dp = new int[m][n];
  int maxSide = 0;

  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)
          ? Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1
          : 1;
        maxSide = Math.max(maxSide, dp[i][j]);
      }
    }
  return maxSide * maxSide;
}

Tips & Gotchas

1dp[i][j] = side length of largest square with bottom-right at (i,j)

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

3Only if current cell is 1

Practice Problems

1Maximal Square
2Count Square Submatrices with All Ones
3Largest Plus Sign

About the Matrix DP & BFS Pattern

Many grid problems are graph problems in disguise. Each cell is a node, adjacent cells are edges. Use BFS for shortest paths, DFS for connectivity, or DP for optimal paths.

Key insight

For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row. Current cell depends on top and left.

Common Matrix Interview Problems

Spiral Matrix
Rotate Image
Search a 2D Matrix
Number of Islands
Maximal Square
Set Matrix Zeroes
Word Search

Frequently Asked Questions

Why take the minimum of three neighbors rather than just two?

The top and left neighbors alone cannot guarantee the diagonal region is filled. A square of side k ending at (i, j) needs squares of side k-1 ending at all three of (i-1, j), (i, j-1), and (i-1, j-1); dropping the diagonal term admits L-shaped regions with a hole at the corner.

Does the same recurrence find the maximal rectangle of ones?

No. Rectangles lack the symmetric bottleneck property that makes the square recurrence work. Maximal Rectangle is solved differently, typically by treating each row as a histogram base and running the largest-rectangle-in-histogram stack algorithm per row, for O(m*n) total.