Maximal Square

Medium#2212d table

A grid holds 0s and 1s. Find the biggest square made only of 1s and return its area. Our example: [1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]. The biggest square of 1s is 3 × 3, so the answer is 9.

221 Maximal SquareWalkthrough · 1×

Example: a 4 × 4 grid with 0s in two corners. Watch (2, 3): to the left a 3 × 3 square ends, but the 0 at (0, 3) leaves only 1 above, so (2, 3) gets 2.

012301231110111111110111
a 1 of the grid, not reached yeta 0 of the gridside of the biggest square ending herethis stepthe smallest neighbour, read fromthe biggest square

dp[r][c]: the side of the biggest square of 1s whose bottom-right corner is (r, c). All 0 to begin with

01/34
restart · back · play · step
Speed
1function maximalSquare(grid):
2 dp = table of the grid's size, all 0
3 side = 0
4 for each cell (r, c), row by row:
5 if grid[r][c] == 1:
6 up = dp[r - 1][c], or 0 off the grid
7 left = dp[r][c - 1], or 0 off the grid
8 diag = dp[r - 1][c - 1], or 0 off the grid
9 dp[r][c] = 1 + min(up, left, diag)
10 side = max(side, dp[r][c])
11 return side * side
state
dp
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
side
–
r
–
c
–
up
–
left
–
diag
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A k × k square of 1s with its corner at (r, c) contains the (k - 1) × (k - 1) squares ending above, to the left and on the diagonal. So it exists exactly when all three of those cells reach k - 1: dp is 1 + the smallest of them.
  2. The smallest one is the limit: at (2, 3) the left reaches 3 and the diagonal 2, but up is 1, because the 0 at (0, 3) breaks every bigger square there.
  3. Row by row, the three cells a cell reads are filled before it, and side keeps the biggest value seen, so the area is side × side at the end.

Complexity

Time O(m × n): each cell reads three neighbours once. Memory O(m × n) for the table; a cell reads only its row and the row above, so two rows are enough.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.