You are given an m x n binary matrix where every cell is 0 or 1.
Find the largest square submatrix that contains only 1s — the square's sides must run along the grid's rows and columns (no rotation) — and return its area (side length squared).
If the grid has no 1 at all, return 0.
Example
The 2x2 block of 1s at rows 1-2, columns 2-3 is the largest all-1s square; area = 2*2 = 4.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] is 0 or 1.
Intuition
A first pass tries every cell as the top-left corner of a candidate square and, for each one, checks every side length that could still fit — re-scanning all the cells inside that candidate square for a 0 each time.
function maximalSquare(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
let maxSide = 0;
// Checks whether every cell in the side x side square starting at (row, col) is a 1.
function isAllOnes(row, col, side) {
for (let i = row; i < row + side; i++) {
for (let j = col; j < col + side; j++) {
if (matrix[i][j] !== 1) return false;
}
}
return true;
}
// Try every cell as a top-left corner.
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
const maxPossibleSide = Math.min(rows - i, cols - j);
// Try the largest side that could still beat the current best first, so we can stop as
// soon as one fits — nothing bigger will start at this corner.
for (let side = maxPossibleSide; side > maxSide; side--) {
if (isAllOnes(i, j, side)) {
maxSide = side;
break;
}
}
}
}
return maxSide * maxSide;
}This is O(rows·cols·min(rows,cols)³) — far more work than necessary. Can we do better?
Checking a 3x3 square from scratch re-verifies nine cells that three separate 1x1 squares and a 2x2 square already verified on their own, one row and column ago. The "is this square all 1s" answer for a smaller square is thrown away instead of reused — that's the overlapping-subproblems signature dynamic programming exists to eliminate, the same one Unique Paths uses to turn a re-derived path count into a single table fill.
The key observation: the largest square that can end with its bottom-right corner at (i, j) is bottlenecked by the largest squares ending at its three neighbours — directly above, directly to the left, and diagonally up-left. Whichever of those three supports the smallest square caps how far (i, j) can grow; (i, j) can add at most one more ring on top of that smallest neighbour. So instead of re-verifying whole squares, fill a table dp[i][j] — the side length of the largest all-1s square ending at (i, j) — bottom-up: it's 0 wherever the matrix has a 0, and otherwise 1 + min(up, left, diagonal). The answer is the largest dp value anywhere, squared (its area).
Walking it through:
dp[i][j] = side length of the largest all-1s square ending at (i, j)
Row 0 and column 0 have no room above or to the left, so each can only ever be a 1x1 square — a matrix cell of 1 seeds a dp value of 1, and a 0 seeds a 0.
All three neighbours already support a 1x1 square, so this cell grows to a 2x2 — the square (0,0)-(1,1) is entirely 1s.
matrix[1][3] is a 1, but the neighbour above is capped at 0 by the 0 sitting at (0,3) — the weakest neighbour bottlenecks the square, so growth stalls at 1x1 even though three of the four cells here are 1s.
All three neighbours already support a 2x2 square, so this cell grows to a 3x3: rows 0-2, columns 0-2 are entirely 1s. maxSide becomes 3.
The neighbours above (2), to the left (2), and diagonal (3) could have supported a 3x3 square here — but matrix[3][3] itself is a 0, so no square can end on it. The square resets to 0 regardless of how promising its neighbours were.
The largest dp value anywhere in the table is 3, at (2,2) — the 3x3 square spanning rows 0-2, columns 0-2. The function returns the **area**, maxSide * maxSide = 9, not the side length itself.
Optimization
2-D DP — largest square ending at each cell
Let dp[i][j] be the side length of the largest all-1s square whose bottom-right corner is (i, j). A square can only extend to (i, j) if matrix[i][j] is 1, and then it's bottlenecked by its three neighbours — the square can be no bigger than the smallest of the square ending just above, just to the left, and diagonally up-left:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
(treating any out-of-bounds neighbour as 0). If matrix[i][j] is 0, dp[i][j] = 0 — no square can end there. The answer is the largest dp value squared (its area).
O(rows * cols) time and O(rows * cols) space for the DP table (row-optimizable to O(cols) by keeping only the previous row, not needed at these bounds).
function maximalSquare(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
let maxSide = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] !== 1) continue; // dp[i][j] stays 0 — no square ends here
// The square ending at (i, j) is bottlenecked by the smallest of the three
// neighbours (out-of-bounds counts as 0), plus itself.
const up = i > 0 ? dp[i - 1][j] : 0;
const left = j > 0 ? dp[i][j - 1] : 0;
const upLeft = i > 0 && j > 0 ? dp[i - 1][j - 1] : 0;
dp[i][j] = 1 + Math.min(up, left, upLeft);
if (dp[i][j] > maxSide) maxSide = dp[i][j];
}
}
return maxSide * maxSide;
}Complexity analysis
Time complexity: O(rows · cols). Here's why:
- The DP fills each of the
rows * colscells of the table exactly once. - Each cell's value comes from three already-computed neighbours (up, left, diagonal) plus a constant number of comparisons — O(1) work per cell.
So the whole fill costs rows * cols × O(1) = O(rows · cols) — down from the brute force's O(rows·cols·min(rows,cols)³), since each square's "is it all 1s" answer is now derived from its neighbours' already-known answers instead of re-verified from scratch.
Space complexity: O(rows · cols). Here's why:
- The stored solution keeps a full
dptable shaped like the input, one entry per cell. - Nothing else scales with the input —
maxSideand the loop counters are O(1).
Each row of dp only ever reads the row directly above it, so the table is optimizable down to a single rolling row of O(cols) — not needed at the given bounds (up to 300×300), so the stored solution keeps the simpler full table, at O(rows · cols).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| matrix = 0 | 0 | Smallest possible input — a single 0 cell, so no square of 1s exists. |
| matrix = 00 00 | 0 | All-zero grid — regardless of size, a grid with no 1 at all always answers 0. |
| matrix = 100 000 000 | 1 | A single isolated 1 — the smallest possible positive answer, area 1. |
| matrix = 111 111 | 4 | All-ones rectangular grid — capped by the shorter dimension (2 rows), so the best square is 2x2, area 4. |
| matrix = 111 111 110 | 4 | A 0 in one corner blocks the square from growing to 3x3, but two separate 2x2 squares still tie for the max — the answer only needs the largest side, not which square achieved it. |
Try it yourself
Write your solution against the real judge before checking the reference.