TL;DR
DP where dp[i][j] = side of the largest all-ones square ending at (i, j) — O(m × n) time, O(n) space after rolling to one row.
Approach 1 — Brute force
Intuition: treat each '1' cell as a possible top-left corner and grow the square side by side, checking that each new bottom row and right column is all ones, until it fails or runs off the matrix.
def maximalSquare(matrix: list[list[str]]) -> int:
m, n = len(matrix), len(matrix[0])
best = 0
for i in range(m):
for j in range(n):
if matrix[i][j] != "1":
continue
side = 1
while i + side < m and j + side < n:
ok = True
for c in range(j, j + side + 1): # new bottom row
if matrix[i + side][c] != "1":
ok = False
break
for r in range(i, i + side + 1): # new right column
if matrix[r][j + side] != "1":
ok = False
break
if not ok:
break
side += 1
best = max(best, side)
return best * best
Complexity: O(m · n · min(m, n)^2) time, O(1) extra space. Each cell can grow a square up to side min(m, n), and every growth step re-scans a border whose length grows with the side, so the border scans for one cell sum to O(min(m, n)^2).
Why it fails at scale: on a dense 300×300 matrix the incremental border checks sum to roughly 300^4 ≈ 8×10^9 operations, far beyond the O(m × n) work the DP needs.
Approach 2 — Top-down memoization
Define side(i, j) = the side of the largest all-ones square whose bottom-right corner is (i, j). A cell can anchor a side-k square only if its top, left, and top-left neighbors each anchor a side-(k-1) square, so side(i, j) = 1 + min of those three. Cache each (i, j).
from functools import lru_cache
def maximalSquare(matrix: list[list[str]]) -> int:
m, n = len(matrix), len(matrix[0])
@lru_cache(maxsize=None)
def side(i: int, j: int) -> int:
if i < 0 or j < 0 or matrix[i][j] != "1":
return 0
return 1 + min(side(i - 1, j), side(i, j - 1), side(i - 1, j - 1))
best = 0
for i in range(m):
for j in range(n):
best = max(best, side(i, j))
return best * best
Complexity: O(m × n) time and space.
Approach 3 — Bottom-up 2-D table
Table meaning: dp[i][j] = side length of the largest all-ones square whose bottom-right corner is (i, j).
2-D recurrence:
dp[i][j] = 0 if matrix[i][j] == '0'
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if matrix[i][j] == '1'
Each cell depends on its top, left, and top-left neighbors, so filling the table row by row (left to right) ensures all three are ready before they are read:
flowchart LR
TL["dp[i-1][j-1]"] --> CUR["dp[i][j]"]
UP["dp[i-1][j]"] --> CUR
LEFT["dp[i][j-1]"] --> CUR
A padded first row and column of zeros handle the borders. The answer is (max dp)².
def maximalSquare(matrix: list[list[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
best = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == "1":
dp[i][j] = 1 + min(dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1])
best = max(best, dp[i][j])
return best * best
Walkthrough on the first example. The two interior rows/columns of ones produce a dp value of 2 at the cell where a full 2×2 block closes (its top, left, and top-left neighbors all hold 1). No cell reaches 3 because no 3×3 all-ones block exists. best = 2, area 2² = 4.
Complexity: O(m × n) time, O(m × n) space.
Approach 4 — Space-optimized rolling row
dp[i][j] reads the previous row (dp[i-1][j], dp[i-1][j-1]) and the current row’s left neighbor (dp[i][j-1]). Keep one row and a single diag scalar for the top-left value that would otherwise be overwritten.
def maximalSquare(matrix: list[list[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [0] * (n + 1)
best = 0
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save dp[i-1][j] before overwrite
if matrix[i - 1][j - 1] == "1":
dp[j] = 1 + min(dp[j], dp[j - 1], diag)
best = max(best, dp[j])
else:
dp[j] = 0
diag = temp
dp[0] = 0 # left border stays 0 for next row
return best * best
Complexity: O(m × n) time, O(n) space.
Common pitfalls
- Returning the side instead of the area — the problem wants area, so square the best side.
- Using
min vs max — the square is limited by its weakest supporting neighbor, so it must be min of the three; max overcounts and reports squares that aren’t solid.
- String vs int cells — the matrix holds
'1'/'0' characters; compare against the strings (or convert), don’t treat them as integers.
- In the rolled version, forgetting to snapshot
diag (the old top-left) before overwriting dp[j] corrupts the diagonal term.
Pattern takeaway
“Largest shape ending here” is a common 2-D DP reframing: instead of searching over all shapes, define each cell as the best structure it can close, built from its neighbors. The min-of-three-neighbors-plus-one recurrence recurs in square and rectangle problems, where every sub-square of a valid square must also be valid.