Maximal Square
In an m x n grid of 0s and 1s, find the biggest square made entirely of 1s and return how many cells it covers.
Examples
A 2 by 2 square of 1s ends at (2, 3), so the side is 2 and the area is 4.
No two 1s are adjacent, so the biggest square is a single cell.
There is no 1 anywhere, so there is no square at all.
Problem Understanding
We need to find the largest square of 1s.
Example:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Here, distinct 2x2 squares exist. The largest possible is side length 2. Output area: 4.
Algorithm Strategy
dp[i][j] is the side length of the largest all-ones square whose bottom-right corner is at (i, j). Every square has exactly one bottom-right corner, so scanning every cell considers every square.
Recurrence — when matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
Why a minimum. A square of side k ending at (i, j) needs three squares of side k-1 ending above, to the left, and diagonally up-left — all three at once. The weakest of them caps what you can build, so the new side is the smallest plus one.
A '0' ends no square, so dp is 0 there. The answer is the largest side seen anywhere, squared.
Interactive Visualization
Two tables: the matrix on the left, unchanged for the whole run, and dp on the right, filling in. The same cell lights in both, so a claimed square can always be checked against the 1s it is made of.
On a growing cell, three neighbours are outlined — top, left and diagonal. The L they make is the reason the rule takes a minimum: the new square has to fit over all three at once.
Try Empty: the answer is 0, and the run never reaches the recurrence.
Dry Run
Consider a small section:
| Cell | Top | Left | Diag | Min(...) | +1? | Result dp[i][j] |
|---|---|---|---|---|---|---|
| (1,1)='1' | dp[0][1]=0 |
dp[1][0]=1 |
dp[0][0]=1 |
0 | Yes | 1 |
| (2,2)='1' | dp[1][2]=1 |
dp[2][1]=1 |
dp[1][1]=1 |
1 | Yes | 2 |
Edge Cases & Common Mistakes
Common pitfalls:
The matrix holds characters, not numbers. The input is
char[][], so the test ismatrix[i][j] == '1'. Comparing against the number 1 is always false and returns 0.Return the area, not the side. The largest side is what the table tracks; the question asks for side × side.
The top row and left column can only manage side 1. There is no cell above or to the left to build on, so a 1 there is a square of exactly one cell — guarding for it is what keeps the recurrence from reading off the grid.
Solution
One pass over the matrix, tracking the best side as it goes — the lines light up as the figure above steps.
Maximal Square Code
1var maximalSquare = function(matrix) {2 const m = matrix.length, n = matrix[0].length;3 const dp = Array.from({ length: m }, () => new Array(n).fill(0));4 let best = 0;5 for (let i = 0; i < m; i++) {6 for (let j = 0; j < n; j++) {7 if (matrix[i][j] === '0') {8 dp[i][j] = 0;9 continue;10 }11 if (i === 0 || j === 0) {12 dp[i][j] = 1;13 } else {14 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;15 }16 best = Math.max(best, dp[i][j]);17 }18 }19 return best * best;20};
More practice: DSA interview questions with answers · patterns cheat sheet