Maximal Square

Given a 2D binary matrix, find the largest square containing only 1s and return its area. A brute-force check of all squares is too slow.

Why this is worth learning

A square ending at the current cell can grow only as far as all three neighboring squares support it: above, left, and diagonal. The weakest neighbor limits the side length.

Before coding: one-minute experiment

For [["1","1"],["1","0"]], why is the answer 1 rather than 3? What quantity does each DP cell store?

Function signature

func MaximalSquare(matrix [][]byte) int

Inputs / outputs

• matrix: grid of '0' and '1'.
• Return: area of the largest all-1s square.

Example

10100
10111
11111
10010
Largest square has side 2 -> area 4

Constraints

• 1 <= m, n <= 300

Core idea (near-solution)

DP where dp[r][c] is the side length of the largest square ending at (r,c). It depends on top, left, and top-left.

Invariant: dp values for previous row/column are already computed when processing (r,c).

Algorithm (step-by-step)

1. Allocate dp of length n+1 filled with zero, where n is the column count. Entry 0 is the empty left boundary; initialize maxSide=0.
2. For each one-based row r from 1 through m, reset prev=0 for the outside diagonal.
3. For each one-based column c from 1 through n, moving left to right:
   • Save above=dp[c] before writing; dp[c-1] is the new left value and prev is the old diagonal.
   • If matrix[r-1][c-1]=='1', set dp[c]=1+min(above,dp[c-1],prev); otherwise set dp[c]=0.
   • Update maxSide=max(maxSide,dp[c]).
   • Set prev=above, carrying the saved old-row value into the next column.
4. Return maxSide*maxSide, the requested area.

Correctness sketch

Let S(r,c) be the largest all-one square with bottom-right corner (r,c). A zero cell forces S=0. At a one cell, a square of side k+1 requires side-k support above, left, and diagonally above-left; otherwise one of its strips or interior corners contains a missing cell. Conversely, if all three neighbors support side k, their covered regions plus the current one cell cover the entire side-(k+1) square. Hence S=1+min(the three neighbors). Track the maximum side over every corner and square it only for the required area. Save the old diagonal while rolling rows.

Trace (hand walkthrough)

For rows 01 / 11, start with padded dp=[0,0,0].

Cell (one-based)	Byte	Old above	New left	Old diagonal	New side
(1,1)	0	0	0	0	0
(1,2)	1	0	0	0	1
(2,1)	1	0	0	0	1
(2,2)	1	1	1	0	1

At (2,2), using the newly written left value as the diagonal would falsely invent a side-2 square over the top-left zero. The correct largest side is 1 and area is 1.

Pitfalls to avoid

• Confusing area with side length.
• Not resetting dp[c] to 0 when matrix cell is '0'.

Debugging lens

Test a hollow square, all ones, a single row, and a zero that must reset old state. The input contains character bytes '0'/'1', not numeric bytes 0/1, and is not mutated.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Use a rolling dp slice and a prev variable for top-left.

Reconstruction checkpoint

For [["1","1"],["1","0"]], why is the answer 1 rather than 3? What quantity does each DP cell store?

Model answer

The three one cells do not form a filled 2-by-2 square, so the largest square has side 1 and area 1. Each DP cell stores a side length, not a count of nearby ones or an area.

Return to 2D DP · Module quiz