Loading…

mediumDynamic ProgrammingLC #221Frequently asked

Maximal Square

Q: How do you solve Maximal Square using the Brute Force — Test Every Square approach?

When to use it: Say this first to anchor the problem, then flag it as far too slow for a 300×300 grid before pivoting to DP. The most literal reading: a square of 1s is defined by a corner and a side, so enumerate corners and sides and check whether the cells inside are all 1. The cleanest version fixes each cell as the *top-left* corner and grows the square one ring at a time — to go from side `k` to side `k+1` you only need to confirm the new bottom row and right column of the larger square are all 1s. **Why this is the natural first attempt.** The problem literally asks for a square of 1s; brute force just makes 'a square of 1s' executable. No insight about subproblems is required — you mechanically try every possibility and keep the best. Stating it shows you understand the goal before optimizing. **Why it collapses at scale.** The grid can be 300×300 = 90,000 cells, and an all-1s grid lets every corner expand a square up to side 300. The repeated re-scanning of overlapping regions is pure wasted work — the square you validate for one corner shares almost all its cells with the square for the corner next to it, yet brute force re-checks them from scratch. That redundancy is the tell that a DP is hiding here. **The bridge to DP.** Notice that whether a big square *ends* at a cell is almost entirely determined by whether slightly smaller squares end at its neighbours. That overlap — answers that reuse answers one cell over — is exactly what dynamic programming exploits. State the brute force, name its redundancy, then define a per-cell state to remove it. Time complexity: O((mn) · min(m,n)²). Space complexity: O(1).

Q: How do you solve Maximal Square using the 2D Bottom-Up DP — Min of Three Neighbours approach?

When to use it: The core insight they're testing. Lead with the state definition: 'dp[i][j] = side of the largest square whose bottom-right corner is (i, j)'. The unlock is the **state definition**: let `dp[i][j]` be the side length of the largest all-1 square whose *bottom-right* corner is exactly `(i, j)`. Anchoring squares by their bottom-right corner (not top-left) is what makes the recurrence look only *backwards* — at up, left, and up-left — cells we've already computed when scanning top-to-bottom, left-to-right. **Why the recurrence is `min` of three neighbours, plus one.** Suppose `(i, j)` is a 1 and we want the biggest square ending there. For a square of side `k+1` to fit, three smaller squares of side `k` must all exist: one ending directly above (covers the top of the new square), one ending to the left (covers its left side), and one ending diagonally up-left (covers its interior). The new square can only be as large as the *weakest* of those three supports allows — hence `min`, not `max` or sum. Add 1 for the current cell itself. If any neighbour can only support a side-`k` square, the diagonal corner of a side-`(k+1)` square would poke into a 0, so `min` correctly clamps it. **The base case and the reset.** The first row and first column have no top/left/diagonal neighbour, so a 1 there can only ever be a square of side 1 — handled by treating out-of-bounds neighbours as 0. A `'0'` cell sets `dp[i][j] = 0`: no square can end on an empty cell, and this naturally resets any run, so we never need to clear state manually. **Evaluation order and the final answer.** Because each cell depends only on cells above and to the left, a simple row-major double loop guarantees every dependency is ready before we read it. We don't return `dp[m-1][n-1]` — the biggest square can end anywhere — so we track a running `maxSide` across all cells and return `maxSide²` for the area. Time complexity: O(mn). Space complexity: O(mn).

Q: How do you solve Maximal Square using the Space-Optimized DP — One Rolling Row (Optimal) approach?

When to use it: The polish that turns O(mn) space into O(n). Frame it as 'each cell only needs the row above and one diagonal value, so a single row plus a saved corner suffices'. The 2D table never reads more than one row back, so we can collapse it to a **single rolling row** of length `n+1` that we overwrite in place as we move down the grid. Before processing row `i`, the array holds row `i-1`; after the inner loop, it holds row `i`. **The one subtlety: the diagonal gets overwritten.** In the full table, `dp[i][j]` needs `dp[i-1][j-1]` — the up-left diagonal. But in a single array, by the time we reach column `j` we've already overwritten index `j-1` with the *current* row's value, destroying the diagonal we need. The fix is a single scalar, `prev`, that remembers the value at index `j-1` *from the previous row* just before we overwrite it. The dance per cell is: stash `temp = dp[j]` (the old top, which becomes the next iteration's diagonal), compute the new `dp[j]` using `prev` as the diagonal, then set `prev = temp`. **Why this ordering is exact, not approximate.** `dp[j]` before assignment is `dp[i-1][j]` (top); `dp[j-1]` after the previous iteration is `dp[i][j-1]` (left); and `prev` holds `dp[i-1][j-1]` (diagonal). All three are precisely the values the 2D recurrence reads — we've just stored them in three live slots instead of an entire matrix. Reset `prev = 0` at the start of each row so the leftmost column correctly sees a zero diagonal. **Why it matters.** For a 300×300 grid the table is trivial, but the rolling-row pattern is a transferable skill: whenever a 2D DP's recurrence reaches back only one row, it compresses to O(n) space with a saved-diagonal trick. This same compression turns Unique Paths, Minimum Path Sum, and Edit Distance into single-row solutions. Time complexity: O(mn). Space complexity: O(n).

LCPractice

Dynamic Programming · 15 of 44 · 10 min

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return **its area**.

The matrix entries are given as the characters '0' and '1'.

In plain English

Find the side of the biggest solid square of 1s anywhere in the grid, then report its area. The square must be axis-aligned and fully filled with 1s — a single 1 is a valid square of side 1 (area 1).

Examples

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Note: The largest all-1 square has side 2 (the block around rows 1-2, cols 2-3), so the area is 2² = 4.

Example 2

Input: matrix = [["0","1"],["1","0"]]
Output: 1
Note: No 2×2 square of 1s exists, but single 1s do, so the largest side is 1 and the area is 1.

Example 3

Input: matrix = [["0"]]
Output: 0
Note: A lone 0 — no square of 1s at all, so the area is 0.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 300
matrix[i][j] is '0' or '1' (a character)

Clarifying questions4First question: Square or rectangle?Explore questions

Q1.Square or rectangle?
Square — equal sides. If it were any rectangle, that's Maximal Rectangle (LC 85), solved with a histogram + monotonic stack.
Q2.Do you want the area or the side length?
The area. If the largest side is k, the answer is k². A common slip is returning k.
Q3.Are the cells integers or characters?
Characters '0' and '1'. Comparing against the int 1 silently fails — every cell looks like a 0.
Q4.Can the grid be all zeros?
Yes. Then no square exists and the answer is 0. The DP handles this because every dp cell stays 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Let dp[i][j] be the side length of the largest all-1 square whose bottom-right corner is (i, j). If the cell is '1', dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1; if it's '0', dp[i][j] = 0. Track the global max side and return side². Brute force is O((mn)²); the DP is O(mn) time, compressible to O(n) space with a single rolling row.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can invent the right state definition — 'largest square ending at (i, j)' — and justify why the recurrence is the MIN of three neighbours, not the sum or the max.

Where candidates slip

Trying to track squares by their top-left corner (which breaks the recurrence), using max instead of min over the neighbours, or returning the side length instead of the area.

How to stand out

Explain WHY min: a square of side k+1 ending here requires three overlapping squares of side k. Then compress to O(n) space by overwriting a single row and carefully saving the diagonal.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Test Every Square	`O((mn) · min(m,n)²)`	`O(1)`	Say this first to anchor the problem, then flag it as far too slow for a 300×300 grid before pivoting to DP.	Read
2	2D Bottom-Up DP — Min of Three Neighbours	`O(mn)`	`O(mn)`	The core insight they're testing. Lead with the state definition: 'dp[i][j] = side of the largest square whose bottom-right corner is (i, j)'.	Read
3	Space-Optimized DP — One Rolling Row (Optimal)Optimal	`O(mn)`	`O(n)`	The polish that turns O(mn) space into O(n). Frame it as 'each cell only needs the row above and one diagonal value, so a single row plus a saved corner suffices'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLargest all-1 square in a binary gridTry every square brute force?YesNoExplore the full tree

Why the recurrence is min of three neighbours

How to read it:A square of side k+1 ending at X needs three overlapping squares of side k at its top, left, and diagonal. The smallest of them caps the new side.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Test Every Square

TimeO((mn) · min(m,n)²)SpaceO(1)

Say this first to anchor the problem, then flag it as far too slow for a 300×300 grid before pivoting to DP.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget cleverness first: how would you verify a square of a given size exists? Pick a top-left corner and a side length, then check every cell inside is a 1.

2Hint 2Explore hint

For each cell that is a '1', try to grow the largest square whose top-left corner sits there, expanding the side by one as long as the new row and column are all 1s.

3Hint 3Explore hint

Track the biggest valid side seen across all corners; the answer is that side squared.

A · Core idea

The most literal reading: a square of 1s is defined by a corner and a side, so enumerate corners and sides and check whether the cells inside are all 1. The cleanest version fixes each cell as the top-left corner and grows the square one ring at a time — to go from side k to side k+1 you only need to confirm the new bottom row and right column of the larger square are all 1s.

Why this is the natural first attempt. The problem literally asks for a square of 1s; brute force just makes 'a square of 1s' executable. No insight about subproblems is required — you mechanically try every possibility and keep the best. Stating it shows you understand the goal before optimizing.

Why it collapses at scale. The grid can be 300×300 = 90,000 cells, and an all-1s grid lets every corner expand a square up to side 300. The repeated re-scanning of overlapping regions is pure wasted work — the square you validate for one corner shares almost all its cells with the square for the corner next to it, yet brute force re-checks them from scratch. That redundancy is the tell that a DP is hiding here.

The bridge to DP. Notice that whether a big square ends at a cell is almost entirely determined by whether slightly smaller squares end at its neighbours. That overlap — answers that reuse answers one cell over — is exactly what dynamic programming exploits. State the brute force, name its redundancy, then define a per-cell state to remove it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["1","1"],["1","1"]]

corner (0,0), side 1

cell is '1' → side 1 valid

Statebest = 1

Final resultbest side = 2 → area = 4

C · Code with teaching comments

Reference implementation previewpublic int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length; int best = 0; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) {Explore the full code

solution.javaJava

Brute Force — Test Every Square — reference

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int best = 0;
4
    for (int r = 0; r < m; r++) {
5
        for (int c = 0; c < n; c++) {
6
            // Cells are characters — compare to '1', never the int 1. A '0' cell can't
7
            // be a square corner.
8
            if (matrix[r][c] != '1') {
9
                continue;
10
            }
11
            int side = 1;
12
            // Grow the square one ring at a time, but only after bounds-checking the
13
            // new border.
14
            while (r + side < m && c + side < n && validBorder(matrix, r, c, side)) {
15
                side++;
16
            }
17
            // Keep the largest side any corner achieved.
18
            best = Math.max(best, side);
19
        }
20
    }
21
    // Return the AREA — side squared — not the side itself.
22
    return best * best;
23
}
24
 
25
private boolean validBorder(char[][] matrix, int r, int c, int side) {
26
    for (int c2 = c; c2 <= c + side; c2++) {
27
        if (matrix[r + side][c2] != '1') {
28
            return false;
29
        }
30
    }
31
    for (int r2 = r; r2 <= r + side; r2++) {
32
        if (matrix[r2][c + side] != '1') {
33
            return false;
34
        }
35
    }
36
    return true;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO((mn) · min(m,n)²) timeO(1) spaceOpen the invariant and proofExplore the proof

Every brute-force validation re-examines cells its neighbour already examined. When the work for one position overlaps almost entirely with the position beside it, stop enumerating shapes and start defining a per-cell state — that reframe is the whole jump from brute force to grid DP.

ComplexityO((mn) · min(m,n)²) time, O(1) space — There are mn candidate corners; each may expand a square up to side min(m, n), and validating one expansion step scans O(side) new cells — overall roughly O(mn · min(m,n)²) in the worst case (an all-1s grid). No extra storage beyond a few counters.

E · Edge cases and pitfalls5matrix = [["0"]] — The single cell isn't '1', so best stays 0 and the area is 0.Explore edge cases

Edge cases handled

matrix = [["0"]]The single cell isn't '1', so best stays 0 and the area is 0.
all-1s 300×300Worst case: every corner expands a large square, exposing the O((mn)·min²) blowup that motivates DP.

Pitfalls

Comparing matrix[r][c] to 1 instead of '1' — every cell reads as a 0.
Re-scanning the entire square each expansion instead of just the new border — even slower.
Returning the side length instead of side² for the area.

03.2

Approach 2 of 3

2D Bottom-Up DP — Min of Three Neighbours

TimeO(mn)SpaceO(mn)

The core insight they're testing. Lead with the state definition: 'dp[i][j] = side of the largest square whose bottom-right corner is (i, j)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i][j] as the side of the largest all-1 square whose BOTTOM-RIGHT corner sits at (i, j). What does it take for that square to have side k?

2Hint 2Explore hint

A square of side k+1 ending at (i, j) requires three squares of side k ending at the cell above, the cell to the left, and the cell diagonally up-left — all simultaneously.

3Hint 3Explore hint

So if grid[i][j]=='1', dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); else 0. Track the global max side and return its square.

A · Core idea

The unlock is the state definition: let dp[i][j] be the side length of the largest all-1 square whose bottom-right corner is exactly (i, j). Anchoring squares by their bottom-right corner (not top-left) is what makes the recurrence look only backwards — at up, left, and up-left — cells we've already computed when scanning top-to-bottom, left-to-right.

Why the recurrence is `min` of three neighbours, plus one. Suppose (i, j) is a 1 and we want the biggest square ending there. For a square of side k+1 to fit, three smaller squares of side k must all exist: one ending directly above (covers the top of the new square), one ending to the left (covers its left side), and one ending diagonally up-left (covers its interior). The new square can only be as large as the weakest of those three supports allows — hence min, not max or sum. Add 1 for the current cell itself. If any neighbour can only support a side-k square, the diagonal corner of a side-(k+1) square would poke into a 0, so min correctly clamps it.

The base case and the reset. The first row and first column have no top/left/diagonal neighbour, so a 1 there can only ever be a square of side 1 — handled by treating out-of-bounds neighbours as 0. A '0' cell sets dp[i][j] = 0: no square can end on an empty cell, and this naturally resets any run, so we never need to clear state manually.

Evaluation order and the final answer. Because each cell depends only on cells above and to the left, a simple row-major double loop guarantees every dependency is ready before we read it. We don't return dp[m-1][n-1] — the biggest square can end anywhere — so we track a running maxSide across all cells and return maxSide² for the area.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["1","0","1"],["1","1","1"],["1","1","1"]]

Interactive diagram

The three neighbours feeding each cell

row 0

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads only cells already computed in a row-major scan: above, left, and up-left.

Final resultmaxSide = 2 → area = 4

C · Code with teaching comments

Reference implementation previewpublic int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] dp = new int[m + 1][n + 1]; int maxSide = 0; for (int i = 1; i <= m; i++) {Explore the full code

solution.javaJava

2D Bottom-Up DP — Min of Three Neighbours — reference

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    // Pad with an extra top row and left column of zeros so first-row/column cells read
4
    // 0 neighbours without bounds checks.
5
    int[][] dp = new int[m + 1][n + 1];
6
    int maxSide = 0;
7
    for (int i = 1; i <= m; i++) {
8
        for (int j = 1; j <= n; j++) {
9
            // dp index i,j maps to matrix index i-1,j-1 because of the padding offset.
10
            if (matrix[i - 1][j - 1] == '1') {
11
                // min of top, left, diag — the weakest support caps the square — plus 1
12
                // for this cell. This line IS the algorithm.
13
                dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
14
                maxSide = Math.max(maxSide, dp[i][j]);
15
            }
16
        }
17
    }
18
    // The biggest square can end anywhere, so we return the tracked max side squared,
19
    // not dp[m][n].
20
    return maxSide * maxSide;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(mn) timeO(mn) spaceOpen the invariant and proofExplore the proof

The entire problem hinges on choosing 'square ending at this cell as its bottom-right corner' as the state. That phrasing converts a global 2D search into a local recurrence reading three already-computed neighbours. Whenever a grid problem feels global, ask: 'what's the best thing ending exactly here?' — defining the answer per-cell is the heart of grid DP.

ComplexityO(mn) time, O(mn) space — One O(1) recurrence evaluation per cell over an m×n grid = O(mn) time. The full dp table stores one int per cell = O(mn) space.

E · Edge cases and pitfalls5matrix = [["0","0"],["0","0"]] — Every cell is '0', so dp stays all 0 and maxSide = 0 → area 0.Explore edge cases

Edge cases handled

matrix = [["0","0"],["0","0"]]Every cell is '0', so dp stays all 0 and maxSide = 0 → area 0.
single row [["1","1","1"]]No cell has a top neighbour, so min is always 0 → every dp is 1, maxSide = 1, area = 1.

Pitfalls

Using max instead of min over the three neighbours — overcounts squares that don't actually fit.
Anchoring the square at its top-left corner — forces forward dependencies and breaks the scan order.
Returning dp[m][n] instead of the tracked maxSide — the largest square rarely ends in the last cell.

03.3

Approach 3 of 3 · Optimal

Space-Optimized DP — One Rolling Row (Optimal)

TimeO(mn)SpaceO(n)

The polish that turns O(mn) space into O(n). Frame it as 'each cell only needs the row above and one diagonal value, so a single row plus a saved corner suffices'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i][j] only reads the row above (dp[i-1][*]) and the current row to the left. Do you really need all m rows in memory?

2Hint 2Explore hint

Keep just one 1D array of length n+1 and overwrite it row by row. The catch: dp[i-1][j-1] (the diagonal) gets clobbered the moment you compute dp[i][j-1].

3Hint 3Explore hint

Save the diagonal in a 'prev' variable before overwriting each cell: capture the old value, compute the new one, then carry the old value forward as the next diagonal.

A · Core idea

The 2D table never reads more than one row back, so we can collapse it to a single rolling row of length n+1 that we overwrite in place as we move down the grid. Before processing row i, the array holds row i-1; after the inner loop, it holds row i.

The one subtlety: the diagonal gets overwritten. In the full table, dp[i][j] needs dp[i-1][j-1] — the up-left diagonal. But in a single array, by the time we reach column j we've already overwritten index j-1 with the current row's value, destroying the diagonal we need. The fix is a single scalar, prev, that remembers the value at index j-1 from the previous row just before we overwrite it. The dance per cell is: stash temp = dp[j] (the old top, which becomes the next iteration's diagonal), compute the new dp[j] using prev as the diagonal, then set prev = temp.

Why this ordering is exact, not approximate. dp[j] before assignment is dp[i-1][j] (top); dp[j-1] after the previous iteration is dp[i][j-1] (left); and prev holds dp[i-1][j-1] (diagonal). All three are precisely the values the 2D recurrence reads — we've just stored them in three live slots instead of an entire matrix. Reset prev = 0 at the start of each row so the leftmost column correctly sees a zero diagonal.

Why it matters. For a 300×300 grid the table is trivial, but the rolling-row pattern is a transferable skill: whenever a 2D DP's recurrence reaches back only one row, it compresses to O(n) space with a saved-diagonal trick. This same compression turns Unique Paths, Minimum Path Sum, and Edit Distance into single-row solutions.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["0","1"],["1","1"]]

Interactive diagram

Picking the right approach

init

Active call / nodeSupporting contextReturned stateNot active

The decision tree to run before writing code. Maximal Square lands on the grid-DP branch.

Final resultmaxSide = 1 → area = 1

C · Code with teaching comments

solution.javaJava

Space-Optimized DP — One Rolling Row (Optimal) — optimal

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int[] dp = new int[n + 1];
4
    int maxSide = 0, prev = 0;
5
    for (int i = 1; i <= m; i++) {
6
        // Reset the diagonal at the start of each row — the leftmost cell's up-left
7
        // neighbour is out of bounds, i.e. 0.
8
        prev = 0;
9
        for (int j = 1; j <= n; j++) {
10
            // Before overwriting, stash the OLD dp[j] — it's this row's top and becomes
11
            // the NEXT column's diagonal.
12
            int temp = dp[j];
13
            if (matrix[i - 1][j - 1] == '1') {
14
                // dp[j]=top (not yet overwritten), dp[j-1]=left (this row),
15
                // prev=diagonal — the exact three values the 2D version reads.
16
                dp[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], prev));
17
                maxSide = Math.max(maxSide, dp[j]);
18
            } else {
19
                dp[j] = 0;
20
            }
21
            // Carry the stashed top forward so the next column sees it as its diagonal.
22
            prev = temp;
23
        }
24
    }
25
    return maxSide * maxSide;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(mn) timeO(n) spaceOpen the invariant and proofExplore the proof

When a 2D recurrence only looks one row up, you don't need the whole grid — one row plus a saved diagonal scalar is enough. The trick is recognizing that overwriting in place destroys exactly one needed value (the diagonal), so you preserve it in a single temp before each write. That 'stash-then-overwrite' move is the constant-space signature of one-row-back grid DPs.

ComplexityO(mn) time, O(n) space — Same O(mn) cell visits and O(1) work each. Storage is one array of n+1 ints plus a couple of scalars → O(n) space, independent of m.

E · Edge cases and pitfalls5matrix with one column — n = 1; dp has length 2, prev stays 0 each row, so dp[1] is 1 wherever the cell is '1' — area 1 at most.Explore edge cases

Edge cases handled

matrix with one columnn = 1; dp has length 2, prev stays 0 each row, so dp[1] is 1 wherever the cell is '1' — area 1 at most.
all-1s griddp grows monotonically along the diagonal; maxSide reaches min(m, n), area = min(m,n)².

Pitfalls

Forgetting prev = 0 at the start of each row — the leftmost cell inherits a stale diagonal and overcounts.
Reading dp[j] as the diagonal instead of the top — dp[j] before assignment is the top (row above), not the diagonal.
Not resetting dp[j] to 0 on a '0' cell — a stale value from the row above leaks through and corrupts later cells.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length; int[] dp = new int[n + 1]; int maxSide = 0, prev = 0; for (int i = 1; i <= m; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max instead of min over neighbours

A square of side k+1 needs the top, left, AND diagonal squares to all be at least side k. Taking the max assumes one strong neighbour is enough and reports squares that don't actually fit.

Explore the code comparison

Don't write this

dp[i][j] = 1 + Math.max(dp[i - 1][j], Math.max(dp[i][j - 1], dp[i - 1][j - 1]));

Write this instead

dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));

Returning side instead of area

dp tracks side lengths; the problem wants the number of cells, which is side². Returning maxSide passes tiny cases by luck and fails the moment the largest side exceeds 1.

Explore the code comparison

Don't write this

return max_side

Write this instead

return max_side * max_side

Comparing to int 1 instead of char '1'

LeetCode passes the grid as characters. matrix[i][j] == 1 compares a char to an int and is always false, so dp stays all zeros.

Explore the code comparison

Don't write this

if (matrix[i - 1][j - 1] == 1) {

Write this instead

if (matrix[i - 1][j - 1] == '1') {

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

2D grid DP — square side from three neighbours

Code pattern to memorize

if grid[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
else:
    dp[i][j] = 0
# answer = (max side)²

Rules to remember

1dp[i][j] is the side length of the largest square ending at (i, j) as its bottom-right corner — not the area, not a boolean.
2The recurrence is min of the three neighbours plus one — a square can only grow if top, left, AND diagonal all support the same smaller square.
3Return the area (side × side), not the side itself — the prompt asks for the count of cells.
4A '0' cell forces dp = 0: no square can end on an empty cell, which naturally resets the run.
5The grid holds characters '0'/'1', not ints — compare against '1', not 1.

Use this pattern when

Finding the largest axis-aligned square / region in a binary matrix
Each cell's answer depends on its up, left, and up-left neighbours
The shape you want is built incrementally from smaller versions of itself
You can define a state 'best thing ending exactly here' over a grid

Choose another pattern when

You need the largest rectangle, not square → Maximal Rectangle via histogram stacks
Counting all squares of every size → still DP but sum the dp values instead of maxing
The region need not be contiguous / axis-aligned → connected components or geometry
Only the perimeter or a path matters → different DP or BFS

Interview takeaway

Maximal Square is the canonical 'min of three neighbours + 1' grid DP. The leap is defining dp as 'largest square ending HERE' so a 2D shape collapses into a 1-cell-at-a-time recurrence. The same `min(top, left, diag)+1` idea reappears in Count Square Submatrices and underlies the intuition for many matrix DPs.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 2D grid DP with a 'best shape ending at this cell' state. Recognize it when each cell's answer is built from its up/left/diagonal neighbours. Same min(top, left, diag)+1 shape powers Count Square Submatrices; the broader 'state ending here over a grid' idea drives Minimum Path Sum, Unique Paths, and Edit Distance.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Square Submatrices with All Ones
Coming soon
Same min-of-three recurrence, but SUM all dp values instead of maxing — each dp[i][j] also counts how many squares end there.
Maximal Rectangle
Coming soon
Drop the square constraint: build per-row histograms and apply Largest Rectangle in Histogram with a monotonic stack.
Largest Rectangle in Histogram
Coming soon
The stack subroutine behind Maximal Rectangle — worth knowing as its building block.
Largest 1-Bordered Square
Coming soon
Only the BORDER must be 1s; precompute consecutive-1 runs right/down and check border feasibility per size.

Same pattern

←

Edit Distance

Continue · Next problem

Maximum Sum Circular Subarray

mediumDynamic ProgrammingLC #221Frequently asked

Maximal Square

LCPractice

Dynamic Programming · 15 of 44 · 10 min

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return **its area**.

The matrix entries are given as the characters '0' and '1'.

In plain English

Find the side of the biggest solid square of 1s anywhere in the grid, then report its area. The square must be axis-aligned and fully filled with 1s — a single 1 is a valid square of side 1 (area 1).

Examples

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Note: The largest all-1 square has side 2 (the block around rows 1-2, cols 2-3), so the area is 2² = 4.

Example 2

Input: matrix = [["0","1"],["1","0"]]
Output: 1
Note: No 2×2 square of 1s exists, but single 1s do, so the largest side is 1 and the area is 1.

Example 3

Input: matrix = [["0"]]
Output: 0
Note: A lone 0 — no square of 1s at all, so the area is 0.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 300
matrix[i][j] is '0' or '1' (a character)

Clarifying questions4First question: Square or rectangle?Explore questions

Q1.Square or rectangle?
Square — equal sides. If it were any rectangle, that's Maximal Rectangle (LC 85), solved with a histogram + monotonic stack.
Q2.Do you want the area or the side length?
The area. If the largest side is k, the answer is k². A common slip is returning k.
Q3.Are the cells integers or characters?
Characters '0' and '1'. Comparing against the int 1 silently fails — every cell looks like a 0.
Q4.Can the grid be all zeros?
Yes. Then no square exists and the answer is 0. The DP handles this because every dp cell stays 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can invent the right state definition — 'largest square ending at (i, j)' — and justify why the recurrence is the MIN of three neighbours, not the sum or the max.

Where candidates slip

Trying to track squares by their top-left corner (which breaks the recurrence), using max instead of min over the neighbours, or returning the side length instead of the area.

How to stand out

Explain WHY min: a square of side k+1 ending here requires three overlapping squares of side k. Then compress to O(n) space by overwriting a single row and carefully saving the diagonal.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Test Every Square	`O((mn) · min(m,n)²)`	`O(1)`	Say this first to anchor the problem, then flag it as far too slow for a 300×300 grid before pivoting to DP.	Read
2	2D Bottom-Up DP — Min of Three Neighbours	`O(mn)`	`O(mn)`	The core insight they're testing. Lead with the state definition: 'dp[i][j] = side of the largest square whose bottom-right corner is (i, j)'.	Read
3	Space-Optimized DP — One Rolling Row (Optimal)Optimal	`O(mn)`	`O(n)`	The polish that turns O(mn) space into O(n). Frame it as 'each cell only needs the row above and one diagonal value, so a single row plus a saved corner suffices'.	Read

Why the recurrence is min of three neighbours

How to read it:A square of side k+1 ending at X needs three overlapping squares of side k at its top, left, and diagonal. The smallest of them caps the new side.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Test Every Square

TimeO((mn) · min(m,n)²)SpaceO(1)

Say this first to anchor the problem, then flag it as far too slow for a 300×300 grid before pivoting to DP.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget cleverness first: how would you verify a square of a given size exists? Pick a top-left corner and a side length, then check every cell inside is a 1.

2Hint 2Explore hint

For each cell that is a '1', try to grow the largest square whose top-left corner sits there, expanding the side by one as long as the new row and column are all 1s.

3Hint 3Explore hint

Track the biggest valid side seen across all corners; the answer is that side squared.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["1","1"],["1","1"]]

corner (0,0), side 1

cell is '1' → side 1 valid

Statebest = 1

Final resultbest side = 2 → area = 4

C · Code with teaching comments

solution.javaJava

Brute Force — Test Every Square — reference

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int best = 0;
4
    for (int r = 0; r < m; r++) {
5
        for (int c = 0; c < n; c++) {
6
            // Cells are characters — compare to '1', never the int 1. A '0' cell can't
7
            // be a square corner.
8
            if (matrix[r][c] != '1') {
9
                continue;
10
            }
11
            int side = 1;
12
            // Grow the square one ring at a time, but only after bounds-checking the
13
            // new border.
14
            while (r + side < m && c + side < n && validBorder(matrix, r, c, side)) {
15
                side++;
16
            }
17
            // Keep the largest side any corner achieved.
18
            best = Math.max(best, side);
19
        }
20
    }
21
    // Return the AREA — side squared — not the side itself.
22
    return best * best;
23
}
24
 
25
private boolean validBorder(char[][] matrix, int r, int c, int side) {
26
    for (int c2 = c; c2 <= c + side; c2++) {
27
        if (matrix[r + side][c2] != '1') {
28
            return false;
29
        }
30
    }
31
    for (int r2 = r; r2 <= r + side; r2++) {
32
        if (matrix[r2][c + side] != '1') {
33
            return false;
34
        }
35
    }
36
    return true;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO((mn) · min(m,n)²) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5matrix = [["0"]] — The single cell isn't '1', so best stays 0 and the area is 0.Explore edge cases

Edge cases handled

matrix = [["0"]]The single cell isn't '1', so best stays 0 and the area is 0.
all-1s 300×300Worst case: every corner expands a large square, exposing the O((mn)·min²) blowup that motivates DP.

Pitfalls

Comparing matrix[r][c] to 1 instead of '1' — every cell reads as a 0.
Re-scanning the entire square each expansion instead of just the new border — even slower.
Returning the side length instead of side² for the area.

03.2

Approach 2 of 3

2D Bottom-Up DP — Min of Three Neighbours

TimeO(mn)SpaceO(mn)

The core insight they're testing. Lead with the state definition: 'dp[i][j] = side of the largest square whose bottom-right corner is (i, j)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define dp[i][j] as the side of the largest all-1 square whose BOTTOM-RIGHT corner sits at (i, j). What does it take for that square to have side k?

2Hint 2Explore hint

A square of side k+1 ending at (i, j) requires three squares of side k ending at the cell above, the cell to the left, and the cell diagonally up-left — all simultaneously.

3Hint 3Explore hint

So if grid[i][j]=='1', dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); else 0. Track the global max side and return its square.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["1","0","1"],["1","1","1"],["1","1","1"]]

Interactive diagram

The three neighbours feeding each cell

row 0

Active call / nodeSupporting contextReturned stateNot active

dp[i][j] reads only cells already computed in a row-major scan: above, left, and up-left.

Final resultmaxSide = 2 → area = 4

C · Code with teaching comments

solution.javaJava

2D Bottom-Up DP — Min of Three Neighbours — reference

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    // Pad with an extra top row and left column of zeros so first-row/column cells read
4
    // 0 neighbours without bounds checks.
5
    int[][] dp = new int[m + 1][n + 1];
6
    int maxSide = 0;
7
    for (int i = 1; i <= m; i++) {
8
        for (int j = 1; j <= n; j++) {
9
            // dp index i,j maps to matrix index i-1,j-1 because of the padding offset.
10
            if (matrix[i - 1][j - 1] == '1') {
11
                // min of top, left, diag — the weakest support caps the square — plus 1
12
                // for this cell. This line IS the algorithm.
13
                dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
14
                maxSide = Math.max(maxSide, dp[i][j]);
15
            }
16
        }
17
    }
18
    // The biggest square can end anywhere, so we return the tracked max side squared,
19
    // not dp[m][n].
20
    return maxSide * maxSide;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(mn) timeO(mn) spaceOpen the invariant and proofExplore the proof

ComplexityO(mn) time, O(mn) space — One O(1) recurrence evaluation per cell over an m×n grid = O(mn) time. The full dp table stores one int per cell = O(mn) space.

E · Edge cases and pitfalls5matrix = [["0","0"],["0","0"]] — Every cell is '0', so dp stays all 0 and maxSide = 0 → area 0.Explore edge cases

Edge cases handled

matrix = [["0","0"],["0","0"]]Every cell is '0', so dp stays all 0 and maxSide = 0 → area 0.
single row [["1","1","1"]]No cell has a top neighbour, so min is always 0 → every dp is 1, maxSide = 1, area = 1.

Pitfalls

Using max instead of min over the three neighbours — overcounts squares that don't actually fit.
Anchoring the square at its top-left corner — forces forward dependencies and breaks the scan order.
Returning dp[m][n] instead of the tracked maxSide — the largest square rarely ends in the last cell.

03.3

Approach 3 of 3 · Optimal

Space-Optimized DP — One Rolling Row (Optimal)

TimeO(mn)SpaceO(n)

The polish that turns O(mn) space into O(n). Frame it as 'each cell only needs the row above and one diagonal value, so a single row plus a saved corner suffices'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i][j] only reads the row above (dp[i-1][*]) and the current row to the left. Do you really need all m rows in memory?

2Hint 2Explore hint

Keep just one 1D array of length n+1 and overwrite it row by row. The catch: dp[i-1][j-1] (the diagonal) gets clobbered the moment you compute dp[i][j-1].

3Hint 3Explore hint

Save the diagonal in a 'prev' variable before overwriting each cell: capture the old value, compute the new one, then carry the old value forward as the next diagonal.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [["0","1"],["1","1"]]

Interactive diagram

Picking the right approach

init

Active call / nodeSupporting contextReturned stateNot active

The decision tree to run before writing code. Maximal Square lands on the grid-DP branch.

Final resultmaxSide = 1 → area = 1

C · Code with teaching comments

solution.javaJava

Space-Optimized DP — One Rolling Row (Optimal) — optimal

4 teaching notes

1
public int maximalSquare(char[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int[] dp = new int[n + 1];
4
    int maxSide = 0, prev = 0;
5
    for (int i = 1; i <= m; i++) {
6
        // Reset the diagonal at the start of each row — the leftmost cell's up-left
7
        // neighbour is out of bounds, i.e. 0.
8
        prev = 0;
9
        for (int j = 1; j <= n; j++) {
10
            // Before overwriting, stash the OLD dp[j] — it's this row's top and becomes
11
            // the NEXT column's diagonal.
12
            int temp = dp[j];
13
            if (matrix[i - 1][j - 1] == '1') {
14
                // dp[j]=top (not yet overwritten), dp[j-1]=left (this row),
15
                // prev=diagonal — the exact three values the 2D version reads.
16
                dp[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], prev));
17
                maxSide = Math.max(maxSide, dp[j]);
18
            } else {
19
                dp[j] = 0;
20
            }
21
            // Carry the stashed top forward so the next column sees it as its diagonal.
22
            prev = temp;
23
        }
24
    }
25
    return maxSide * maxSide;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(mn) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(mn) time, O(n) space — Same O(mn) cell visits and O(1) work each. Storage is one array of n+1 ints plus a couple of scalars → O(n) space, independent of m.

E · Edge cases and pitfalls5matrix with one column — n = 1; dp has length 2, prev stays 0 each row, so dp[1] is 1 wherever the cell is '1' — area 1 at most.Explore edge cases

Edge cases handled

matrix with one columnn = 1; dp has length 2, prev stays 0 each row, so dp[1] is 1 wherever the cell is '1' — area 1 at most.
all-1s griddp grows monotonically along the diagonal; maxSide reaches min(m, n), area = min(m,n)².

Pitfalls

Forgetting prev = 0 at the start of each row — the leftmost cell inherits a stale diagonal and overcounts.
Reading dp[j] as the diagonal instead of the top — dp[j] before assignment is the top (row above), not the diagonal.
Not resetting dp[j] to 0 on a '0' cell — a stale value from the row above leaks through and corrupts later cells.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max instead of min over neighbours

A square of side k+1 needs the top, left, AND diagonal squares to all be at least side k. Taking the max assumes one strong neighbour is enough and reports squares that don't actually fit.

Explore the code comparison

Don't write this

dp[i][j] = 1 + Math.max(dp[i - 1][j], Math.max(dp[i][j - 1], dp[i - 1][j - 1]));

Write this instead

dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));

Returning side instead of area

dp tracks side lengths; the problem wants the number of cells, which is side². Returning maxSide passes tiny cases by luck and fails the moment the largest side exceeds 1.

Explore the code comparison

Don't write this

return max_side

Write this instead

return max_side * max_side

Comparing to int 1 instead of char '1'

LeetCode passes the grid as characters. matrix[i][j] == 1 compares a char to an int and is always false, so dp stays all zeros.

Explore the code comparison

Don't write this

if (matrix[i - 1][j - 1] == 1) {

Write this instead

if (matrix[i - 1][j - 1] == '1') {

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

2D grid DP — square side from three neighbours

Code pattern to memorize

if grid[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
else:
    dp[i][j] = 0
# answer = (max side)²

Rules to remember

1dp[i][j] is the side length of the largest square ending at (i, j) as its bottom-right corner — not the area, not a boolean.
2The recurrence is min of the three neighbours plus one — a square can only grow if top, left, AND diagonal all support the same smaller square.
3Return the area (side × side), not the side itself — the prompt asks for the count of cells.
4A '0' cell forces dp = 0: no square can end on an empty cell, which naturally resets the run.
5The grid holds characters '0'/'1', not ints — compare against '1', not 1.

Use this pattern when

Finding the largest axis-aligned square / region in a binary matrix
Each cell's answer depends on its up, left, and up-left neighbours
The shape you want is built incrementally from smaller versions of itself
You can define a state 'best thing ending exactly here' over a grid

Choose another pattern when

You need the largest rectangle, not square → Maximal Rectangle via histogram stacks
Counting all squares of every size → still DP but sum the dp values instead of maxing
The region need not be contiguous / axis-aligned → connected components or geometry
Only the perimeter or a path matters → different DP or BFS

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Square Submatrices with All Ones
Coming soon
Same min-of-three recurrence, but SUM all dp values instead of maxing — each dp[i][j] also counts how many squares end there.
Maximal Rectangle
Coming soon
Drop the square constraint: build per-row histograms and apply Largest Rectangle in Histogram with a monotonic stack.
Largest Rectangle in Histogram
Coming soon
The stack subroutine behind Maximal Rectangle — worth knowing as its building block.
Largest 1-Bordered Square
Coming soon
Only the BORDER must be 1s; precompute consecutive-1 runs right/down and check border feasibility per size.

Same pattern

←

Edit Distance

Continue · Next problem

Maximum Sum Circular Subarray