AlgoMaster Logo

Maximal Square

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a 2D grid of characters where each cell is either '0' or '1'. We need to find the largest axis-aligned square region where every cell is '1', then return the area of that square.

The answer is an area, not a side length, so a 3x3 square returns 9. We want squares specifically, not rectangles. The matrix can be up to 300x300, which is 90,000 cells, so the approach has to scale.

The efficient solutions all rest on one reframing: for each cell, what is the largest all-1's square that can end at that cell, using it as the bottom-right corner? If we can answer that for every cell, the largest answer is the side length we want.

Key Constraints:

  • 1 <= m, n <= 300 → The matrix has at most 90,000 cells. An O(m n) solution is about 90,000 operations. A naive O(m^2 n^2) check of every possible square is around 8 billion operations, which is too slow, so the goal is to reach O(m * n).
  • matrix[i][j] is '0' or '1' → The cells are characters, not integers. Comparisons must be against '1' and '0', not the numbers 1 and 0.

Approach 1: Brute Force

Intuition

Try every possible square in the matrix. For each cell, treat it as the top-left corner of a square and expand the side length as far as possible while all cells within the square remain '1'. Track the largest square found.

For a given top-left corner (i, j) and side length k, verify that all k*k cells inside the square are '1'. If any cell is '0', that side length (and anything bigger) cannot work for this corner, so the expansion stops there.

Algorithm

  1. Initialize maxSide = 0 to track the largest square side length found.
  2. For each cell (i, j) in the matrix where matrix[i][j] == '1':
    • Determine the maximum possible side length from this cell: maxK = min(m - i, n - j).
    • For each side length k from 1 to maxK:
      • Check if all cells in the square from (i, j) to (i+k-1, j+k-1) are '1'.
      • If yes, update maxSide = max(maxSide, k).
      • If no, stop expanding from this corner.
  3. Return maxSide * maxSide.

Example Walkthrough

Input:

0
1
2
3
4
0
1
0
1
0
0
1
1
0
1
1
1
2
1
1
1
1
1
3
1
0
0
1
0
matrix

We try each '1' cell as a top-left corner and expand. Most corners reach only side 1 before hitting a '0'. For example, corner (0,0) cannot reach side 2 because the 2x2 square would include (0,1), which is '0'. Corner (2,1) also stops at side 1 because the 2x2 square would include (3,2), which is '0'.

The best corner is (1,2). A 2x2 square there covers rows 1-2 and columns 2-3, all of which are '1', so side 2 works. Expanding to 3x3 would need rows 1-3 and columns 2-4, but (3,2) is '0', so it fails. No other corner produces a square larger than side 2. The maximum side is 2, so the area is 2 * 2 = 4.

4
result

Code

This approach re-scans overlapping regions for every cell. The next approach removes that repeated work by computing the largest square ending at each cell from results already computed for its neighbors.

Approach 2: Dynamic Programming (2D Table)

Intuition

Instead of asking "what is the biggest square starting at this cell?", ask "what is the biggest square whose bottom-right corner is this cell?" That second question has a recurrence the first does not.

Define dp[i][j] as the side length of the largest all-1's square with its bottom-right corner at position (i, j). If matrix[i][j] is '0', then dp[i][j] = 0 since no all-1's square can end at a '0' cell.

For cell (i, j) to be the bottom-right corner of a k x k square of 1's, three conditions must hold at once:

  • The cell directly above, (i-1, j), must be the bottom-right corner of at least a (k-1) x (k-1) square.
  • The cell to the left, (i, j-1), must be the bottom-right corner of at least a (k-1) x (k-1) square.
  • The cell diagonally above-left, (i-1, j-1), must be the bottom-right corner of at least a (k-1) x (k-1) square.

If any of these three neighbors has a smaller value, that neighbor limits how far the square can extend. The recurrence is:

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

Algorithm

  1. Create a 2D array dp of size (m+1) x (n+1), initialized to 0. The extra row and column handle boundary conditions cleanly.
  2. Initialize maxSide = 0.
  3. For each cell (i, j) from (1,1) to (m, n):
    • If matrix[i-1][j-1] == '1' (using 1-indexed dp with 0-indexed matrix):
      • dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
      • Update maxSide = max(maxSide, dp[i][j])
  4. Return maxSide * maxSide.

Example Walkthrough

Using the same matrix as before, we fill a dp grid one row at a time. Each '1' cell takes the minimum of its top, left, and diagonal neighbors and adds 1; each '0' cell stays 0. The animation below tracks the dp values and the running maximum.

1Row 0: Copy matrix values. dp=1 where matrix='1', else 0. maxSide=1
0
1
2
3
4
0
1
0
1
0
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
1/7

The largest dp value is 2, reached at (2,3) and (2,4). That marks a 2x2 square of 1's ending at those corners, so the area is 2 * 2 = 4.

Code

The dp table uses O(m * n) space, but computing row i only reads row i and row i-1. The next approach keeps a single row, dropping the space to O(n).

Approach 3: Space-Optimized DP (1D Array)

Intuition

In the recurrence dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, all three values come from either the current row or the immediately preceding row. The 2D table can collapse into a single 1D array of length n+1. As we process each row left to right, the array transitions from holding the previous row's values to holding the current row's.

The one complication is dp[i-1][j-1], the diagonal. By the time we process column j, position j-1 in the array already holds the current row's value, so the previous row's diagonal value has been overwritten. We keep it in a separate variable, saved one step before it gets overwritten.

Algorithm

  1. Create a 1D array dp of size n+1, initialized to 0.
  2. Initialize maxSide = 0 and a variable prev = 0 to track the diagonal value.
  3. For each row i from 0 to m-1:
    • For each column j from 1 to n:
      • Save the current dp[j] in temp (this will be prev for the next column).
      • If matrix[i][j-1] == '1':
        • dp[j] = min(dp[j], dp[j-1], prev) + 1
        • Update maxSide if needed.
      • Else: dp[j] = 0.
      • Set prev = temp.
    • Reset prev = 0 at the start of each row.
  4. Return maxSide * maxSide.

Example Walkthrough

This trace uses a 3x3 matrix of all 1's, which grows the square in every row and exercises the diagonal carry through prev. The dp array has length n+1 = 4. Index 0 stays 0 as a left boundary, and indices 1 through 3 hold the current row's values for columns 0 through 2 of the matrix.

1Initialize dp=[0,0,0,0] (size n+1=4), prev=0
0
0
1
0
2
0
3
0
1/8

The running maximum reaches 3 when dp[3] becomes 3, which corresponds to the full 3x3 square. The area is 3 * 3 = 9.

Code