The largest square of ones
Given a grid of 0s and 1s, return the area of the largest square containing only
1s.
Examples
| Input | Output | Why |
|---|---|---|
grid = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] | 4 | A 2 × 2 square in the middle right. |
grid = [[0,1],[1,0]] | 1 | Single cells only. |
grid = [[0]] | 0 | No ones. |
Constraints
- 1 ≤ rows, cols ≤ 300
- Every cell is 0 or 1
Hints
Hint 1
Let side[r][c] be the side of the largest all-ones square whose bottom-right corner is (r, c).
Hint 2
For a 1: side = 1 + min(side above, side to the left, side diagonally up-left).
Hint 3
The answer is the largest side, squared.
Where people lose marks
- Returning the side instead of the area.
- Using only the up and left neighbours, which allows an L-shaped hole at the diagonal.
Dry run on [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4
Row 0 filled.
-
Step 2 / 4
Row 1 filled.
-
Step 3 / 4
Row 2 filled.
-
Step 4 / 4
Row 3 filled. The largest side is 2: area 4.
How to think about it
Let side[r][c] be the side of the largest square of ones with its bottom-right corner at (r, c). A square
of side k ending there needs squares of side k − 1 ending at the cell above, the cell to the left and the cell
diagonally up-left, so side = 1 + min(up, left, diagonal) for a 1 and 0 for a 0. The minimum is exactly the
limiting neighbour. Keep the largest side and return its square.
Complexity. Time O(rows · cols) · Space O(cols)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def maximal_square(grid):
cols = len(grid[0])
side = [0] * (cols + 1) # side[c + 1]: square ending at column c, previous row
best = 0
for row in grid:
diag = 0 # side[c] of the previous row, before it is overwritten
for c in range(cols):
above = side[c + 1]
side[c + 1] = 1 + min(above, side[c], diag) if row[c] == 1 else 0
diag = above
best = max(best, side[c + 1])
return best * best#include <algorithm>
#include <vector>
int solve(const std::vector<std::vector<int>>& grid) {
const int cols = grid[0].size();
std::vector<int> side(cols + 1, 0);
int best = 0;
for (const auto& row : grid) {
int diag = 0; // up-left value from the previous row
for (int c = 0; c < cols; ++c) {
int above = side[c + 1];
side[c + 1] = row[c] == 1 ? 1 + std::min({above, side[c], diag}) : 0;
diag = above;
best = std::max(best, side[c + 1]);
}
}
return best * best;
}class Solution {
public int maximalSquare(int[][] grid) {
int cols = grid[0].length, best = 0;
int[] side = new int[cols + 1];
for (int[] row : grid) {
int diag = 0; // up-left value from the previous row
for (int c = 0; c < cols; c++) {
int above = side[c + 1];
side[c + 1] = row[c] == 1 ? 1 + Math.min(above, Math.min(side[c], diag)) : 0;
diag = above;
best = Math.max(best, side[c + 1]);
}
}
return best * best;
}
}function maximalSquare(grid) {
const cols = grid[0].length, side = new Array(cols + 1).fill(0);
let best = 0;
for (const row of grid) {
let diag = 0; // up-left value from the previous row
for (let c = 0; c < cols; c++) {
const above = side[c + 1];
side[c + 1] = row[c] === 1 ? 1 + Math.min(above, side[c], diag) : 0;
diag = above;
best = Math.max(best, side[c + 1]);
}
}
return best * best;
}fn solve<const C: usize>(grid: &[[i64; C]]) -> i64 {
let mut side = vec![0i64; C + 1];
let mut best = 0;
for row in grid {
let mut diag = 0; // up-left value from the previous row
for c in 0..C {
let above = side[c + 1];
side[c + 1] = if row[c] == 1 { 1 + above.min(side[c]).min(diag) } else { 0 };
diag = above;
best = best.max(side[c + 1]);
}
}
best * best
}solve :: [[Int]] -> Int
solve grid = let s = maximum (0 : concat rows) in s * s
where
width = length (head grid)
rows = tail (scanl nextRow (replicate width 0) grid)
-- side of the largest square ending at each cell, from the previous row of sides
nextRow above row = tail (scanl3 row above)
scanl3 row above = scanl (\left (cell, up, diag) -> if cell == 1 then 1 + minimum [up, left, diag] else 0) 0 (zip3 row above (0 : above))Variants to try
- Count all square submatrices of ones (sum the side values).
- The largest rectangle of ones: a histogram per row with a monotonic stack.
- Largest plus sign of ones: four direction tables.
Next problems
The cheapest path through a grid
Move only right or down from the top-left cell to the bottom-right one, paying each cell's cost. Each cell's cheapest arrival comes from above or the left.
Open the problem → Medium15 minPaths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Hard30 minThe least starting health
Cross a grid of gains and losses, right or down, without health ever dropping to zero. The requirement at a cell depends on what comes after, so fill from the end.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest path through a grid
Move only right or down from the top-left cell to the bottom-right one, paying each cell's cost. Each cell's cheapest arrival comes from above or the left.
Open the problem → Medium15 minPaths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Hard30 minThe least starting health
Cross a grid of gains and losses, right or down, without health ever dropping to zero. The requirement at a cell depends on what comes after, so fill from the end.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.