Problem Statement

Maximal Square

You are given a grid (a table of rows and columns) filled with only two characters: "0" and "1". Your job is to find the biggest square you can draw inside the grid that is made of all "1"s, and return its area (side times side). A square means equal width and height, like a 2 by 2 or 3 by 3 block. The trick that makes this easy is to keep a second grid that remembers, for each cell, the side length of the biggest all-1s square whose bottom-right corner sits on that cell. This second grid is called a DP table (DP stands for dynamic programming, which just means we solve big problems by saving the answers to smaller ones and reusing them). Here is the key rule: if a cell holds "1", the biggest square ending there is one more than the smallest of its three already-solved neighbors, the cell above, the cell to the left, and the cell diagonally up-left. The smallest neighbor is the bottleneck, because the square can only grow as far as its weakest side allows.

mediumDynamic ProgrammingMatrixDynamic ProgrammingTime: O(m * n) · Space: O(m * n)

Signals to notice

largest square of 1s in binary matrixextend squares from smaller onescheck three neighbors

Brute force first

For each cell, expand outward checking if the square is all 1s — or. Each cell independently expands. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

DP: dp[i][j] = side length of largest square with bottom-right at (i,j). If grid[i][j] == 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The minimum of the three neighbors determines the largest square you can extend. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `matrix=[["0","1"],["1","0"]]`

init: dp=[[0,0],[0,0]], max_side=0
(0,0)='0': skip -> dp[0][0]=0, max_side=0
(0,1)='1', i==0 edge -> dp[0][1]=1, max_side=1
(1,0)='1', j==0 edge -> dp[1][0]=1, max_side=1
(1,1)='0': skip -> dp[1][1]=0, max_side=1
return max_side*max_side = 1*1 = 1

What must stay true

A square of side k at (i,j) exists only if squares of side k-1 exist at the top, left, and top-left neighbors. The minimum of those three determines how large the current square can be — the weakest link limits the extension. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

dp = grid of zeros; max_side = 0
for i in rows:
  for j in cols:
    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
      max_side = max(max_side, dp[i][j])
return max_side * max_side

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not understanding WHY it's the minimum — if any neighbor has a smaller square, that dimension constrains the current square. You can't form a 4×4 square if your left neighbor only supports a 2×2. The fix is usually to return to the meaning of each move, not just the steps themselves.

Dynamic Programming Pattern