#221 Maximal Square
frequently reported atPayPalByteDance / TikTokAirbnbGoogleAppleFlipkart
the problem
In plain words
A grid holds the characters '0' and '1' (a char[][]). Return the area of the largest square made only of '1's.
in matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
out 4
A 2 × 2 square of '1's, for example rows 1–2, columns 3–4.
in matrix = [["0","1"],["1","0"]]
out 1
in matrix = [["0"]]
out 0
- 1 ≤ m, n ≤ 300
- matrix[r][c] is '0' or '1'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGrid DP
Let dp[r][c] be the side of the biggest all-'1' square whose bottom-right corner is (r, c). It can grow only as far as its smallest neighbour square (above, left, up-left) allows: dp = 1 + min(up, left, up-left).
solutions
From brute force to optimal
For each cell as the top-left corner, grow the square while its new bottom row and right column are all '1'.
- k = 0; while the (k + 1)-square fits and its new edge is all '1': k++.
- Track the biggest k; return k².
m·n corners; each can grow up to min(m, n) times, checking up to 2·min(m, n) cells per growth.
A few counters.
class Solution { public int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length, side = 0; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { // grow a square with its top-left corner at (r, c) while it stays all '1' int k = 0; while (r + k < m && c + k < n && edgeIsAllOnes(matrix, r, c, k)) k++; side = Math.max(side, k); } } return side * side; } /** Are the new bottom row and right column of a (k+1) × (k+1) square at (r, c) all '1'? */ private boolean edgeIsAllOnes(char[][] matrix, int r, int c, int k) { for (int i = 0; i <= k; i++) { if (matrix[r + k][c + i] != '1' || matrix[r + i][c + k] != '1') return false; } return true; }}dp[r + 1][c + 1] = 1 + min(dp[r][c], dp[r][c + 1], dp[r + 1][c]) for a '1', else 0.
- Pad the table with a zero row and column so edges need no checks.
- Keep the largest side seen.
- Return side × side.
One O(1) step per cell.
The (m + 1) × (n + 1) table.
class Solution { public int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length, side = 0; int[][] dp = new int[m + 1][n + 1]; // dp[r+1][c+1] = side of the biggest square ENDING at (r, c) for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (matrix[r][c] == '1') { // limited by the smallest of the squares above, to the left and up-left dp[r + 1][c + 1] = 1 + Math.min(dp[r][c], Math.min(dp[r][c + 1], dp[r + 1][c])); side = Math.max(side, dp[r + 1][c + 1]); } } } return side * side; // area, not side }}Each cell reads up, left and up-left — keep one row and save the old value as the next diagonal.
- up = dp[c + 1] (previous row) before overwriting.
- dp[c + 1] = '1' ? 1 + min(diag, up, dp[c]) : 0.
- diag = up.
Same cells.
One row of n + 1 ints.
class Solution { public int maximalSquare(char[][] matrix) { int n = matrix[0].length, side = 0; int[] dp = new int[n + 1]; // dp[c+1] = square ending at column c in the current row for (char[] row : matrix) { int diag = 0; // dp of the up-left cell (previous row, previous column) for (int c = 0; c < n; c++) { int up = dp[c + 1]; // previous row's value, about to be overwritten dp[c + 1] = row[c] == '1' ? 1 + Math.min(diag, Math.min(up, dp[c])) : 0; side = Math.max(side, dp[c + 1]); diag = up; } } return side * side; }}in the room
How to say it in the interview
talk track
- Define the state as the bottom-right corner — say it out loud, it's the whole trick.
- Explain why it's the MIN of three neighbours: one short neighbour limits the square.
- Return side × side — the question asks for the area.
traps
- Returning the side instead of the area.
- Comparing with 1 instead of '1': the grid holds chars, and (int) '1' is 49.
- Using max instead of min of the three neighbours.
what they ask next
Follow-ups
Largest rectangle of '1's (LC 85)?
Build histogram heights row by row, then run Largest Rectangle in Histogram on each row: O(m·n) with a monotonic stack.
Count all squares of '1's (LC 1277)?
Same dp; the answer is the sum of all dp values, because a corner with dp = k ends exactly k squares.
before you submit
Edge cases to test
- No '1' at all → 0.
- A single row of '1's → 1: a 1 × 1 square, not a line.
- A 3 × 2 block of '1's → 4: the square is limited by the shorter side.
practise next
Similar problems
- #64Minimum Path SumMediumin Dynamic Programming
- #84Largest Rectangle in HistogramHardin Stacks
- #304Range Sum Query 2D - ImmutableMediumin Hashing