Medium Problemsgridoptimization

Maximum size square sub-matrix with all 1s

Given a binary matrix of 0s and 1s, find the side length of the largest square submatrix made up entirely of 1s.

Do this lesson first: longest common subsequence

Example input

a 9 by 9 binary matrix, rows top to bottom: 101011111 / 011011011 / 011111101 / 111111111 / 001111111 / 010011111 / 101011110 / 010011111 / 101010101

Expected output

4

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] is the side length of the largest square made up entirely of 1s whose BOTTOM-RIGHT CORNER sits exactly at row r, column c. Not the largest square found anywhere so far, and not the largest square that happens to touch this cell somewhere: the corner is pinned here, and the square extends up and to the left from it. dp[r][c] = 3 therefore means a 3 by 3 block of 1s occupies rows r - 2 through r and columns c - 2 through c, and nothing else. Pinning the corner is the entire insight of this page, and reading the cell as 'the biggest square seen up to here' is the misreading that makes the recurrence look impossible, because a biggest-so-far number has no local rule that produces it. Since every cell answers about the square ending at itself, no cell you can name in advance holds the problem's answer; some cell does hold it, but which one depends on the input, so the answer is the largest number the finished table contains.

dp[r][c] = 0 where the matrix holds a 0, else 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])

Ask how large a square can end at (r, c). If the matrix holds a 0 there, none can, at any size, because every square ending at that corner has to stand on that cell. Otherwise the side is at least 1, and the question becomes what stops it being larger. A square of side k cornered at (r, c) contains three squares of side k - 1 inside it: one cornered at (r - 1, c) directly above, one cornered at (r, c - 1) to the left, and one cornered at (r - 1, c - 1) diagonally up and to the left. All three have to exist, so k - 1 cannot exceed the smallest of those three answers; and going the other way, if all three do reach k - 1 then together with this cell's own 1 they tile the whole k by k block with nothing left uncovered. So the side is one more than the SMALLEST of the three. This is the first three-way comparison in the course, and the third candidate is not decoration: the diagonal neighbour is the only one of the three that can see a hole sitting up and to the left, and dropping it is the standard way to get this problem wrong.

Row 0 and column 0 are declared rather than derived, for a reason that is the recurrence in miniature: a square cornered in the top row has no room above it and a square cornered in the left column has no room to its left, so neither can have a side above 1. Each of those cells is simply a copy of the input, 1 where the matrix holds a 1 and 0 where it holds a 0. Every interior cell is computed, including the ones standing on a 0: those resolve to 0 without consulting a single neighbour, because no neighbour value could rescue a square that has to stand on a 0, so nothing is read and there is nothing to predict. Filling row-major, left to right within each row, means all three neighbours are final before they are used, which is the only ordering property the recurrence needs, and notice that the diagonal one costs nothing extra: a row-major sweep finished the whole previous row before it started this one.

Tabulation over all size times size cells. Every cell has to hold its own answer, the zeros included, because the cells to its right and below will read it, so there is nothing for a top-down solve to skip and memoization would only add call overhead. A cell reads the row above and its own left neighbour, so two rows of storage are enough, or one rolling row if you stash the diagonal value in a temporary before you overwrite it. This is the same row-major sweep over the same (row, column) state as min-cost-path and count-all-paths-in-a-grid; what is new is that a cell has three dependencies instead of two, and that the answer is not the last cell but the largest cell, so a running best has to travel with the sweep. Watch the slider while you are here: the answer goes 2, 2, 3, 3, 3, 4, 4 as the board grows from 3 to 9, so it plateaus for three sizes in a row. A bigger board does not always contain a bigger square, and the answer only moves when the sweep finally reaches the bottom-right corner of a genuinely larger block of 1s.

Time O(rows × cols)Space O(rows × cols), reducible to O(cols) with one rolling row plus one saved diagonal

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 and column 0 are declared rather than derived, for a reason that is the recurrence in miniature: a square cornered in the top row has no room above it and a square cornered in the left column has no room to its left, so neither can have a side above 1. Each of those cells is simply a copy of the input, 1 where the matrix holds a 1 and 0 where it holds a 0. Every interior cell is computed, including the ones standing on a 0: those resolve to 0 without consulting a single neighbour, because no neighbour value could rescue a square that has to stand on a 0, so nothing is read and there is nothing to predict. Filling row-major, left to right within each row, means all three neighbours are final before they are used, which is the only ordering property the recurrence needs, and notice that the diagonal one costs nothing extra: a row-major sweep finished the whole previous row before it started this one.

row r

0

1

2

3

4

5

6

7

8

0

1

0

1

0

1

0

1

0

1

2

0

1

2

0

1

2

1

2

1

0

1

3

1

2

1

4

0

1

2

3

2

5

0

1

0

1

2

3

6

1

0

1

0

1

2

3

4

0

7

0

1

0

1

2

3

4

1

8

1

0

1

0

1

0

1

0

1

column c: side of the largest all-ones square cornered at (r, c)

maximum-square-submatrix-of-ones.ts

1function maximalSquare(matrix) {
2 const n = matrix.length, m = matrix[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(0));
4 for (let c = 0; c < m; c++) dp[0][c] = matrix[0][c];
5 for (let r = 0; r < n; r++) dp[r][0] = matrix[r][0];
6 for (let r = 1; r < n; r++) {
7 for (let c = 1; c < m; c++) {
8 if (matrix[r][c] === 0) continue;
9 const above = dp[r - 1][c], left = dp[r][c - 1];
10 dp[r][c] = 1 + Math.min(above, left, dp[r - 1][c - 1]);
11 }
12 }
13 let best = 0;
14 for (const row of dp) best = Math.max(best, ...row);
15 return best;
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

maximum-square-submatrix-of-ones.ts

1function maximalSquare(matrix) {
2 const n = matrix.length, m = matrix[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(0));
4 for (let c = 0; c < m; c++) dp[0][c] = matrix[0][c];
5 for (let r = 0; r < n; r++) dp[r][0] = matrix[r][0];
6 for (let r = 1; r < n; r++) {
7 for (let c = 1; c < m; c++) {
8 if (matrix[r][c] === 0) continue;
9 const above = dp[r - 1][c], left = dp[r][c - 1];
10 dp[r][c] = 1 + Math.min(above, left, dp[r - 1][c - 1]);
11 }
12 }
13 let best = 0;
14 for (const row of dp) best = Math.max(best, ...row);
15 return best;
16}

Where people go wrong

Reading a cell as 'the largest square anywhere in the board so far'. It is not: it is the largest square whose bottom-right corner is exactly that cell, which is why a cell can fall back to 0 or 1 while a far bigger square already sits elsewhere in the table, and why the answer has to be a scan over the whole table rather than the value in the last cell. Here the answer 4 sits at row 6, column 7 while the last cell holds 1. The second trap is taking the min of only two neighbours, above and left, and forgetting the diagonal, and it is not a matter of style: at row 1, column 2 of this matrix the cell above holds 1 and the cell to the left holds 1, so a two-way min writes 2 and claims a 2 by 2 block of 1s at rows 0 to 1, columns 1 to 2. There is a 0 at row 0, column 1. The diagonal neighbour, holding 0, is the only one of the three that sees it, and it is what pulls the cell back to the correct 1.

Return the AREA of the largest square rather than its side.
Square the answer at the very end and change nothing else. The table still has to hold sides, because a side is what the plus-one and the min of three operate on; areas do not compose that way, since the side of the enclosing square is one more than the side of its sub-squares while its area is not one more than theirs.
Find the largest all-ones RECTANGLE instead of the largest square.
The recurrence breaks, and the reason is worth understanding: a square cornered at a cell is described by one number, its side, but a rectangle cornered there is not, so a cell would have to remember every width and height combination that fits. The usual route is different in kind, a per-column count of consecutive 1s plus a largest-rectangle-in-a-histogram scan per row, which is not this table.
Ask for the largest square whose BORDER is all 1s, with its interior unrestricted.
A different and larger answer: on this same matrix the bordered answer at the full board is 5 against the solid 4. One number per cell no longer suffices, since a run of 1s going up and a run going left both have to be tracked to close a border, so the state grows a second number per cell. That is largest-x-bordered-square, and comparing the two is the point of having both pages.

Longest Subsequence with 1 adjacent difference Bellman–Ford Algorithm