DSA Maximal Square
Maximal Square stores at each cell the side length of the largest all-ones square ending at that cell. A cell grows a square only as far as its three smallest neighbours allow.
The problem
Maximal Square asks for the area of the largest square made only of ones inside a grid of zeros and ones. The square must be solid. Every cell inside it must hold a one.
The input is the grid. The output is one number, an area. A square of side two has area four, and a square of side three has area nine.
The cases used in this article
matrix_a = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0],
]
matrix_b = [
[0, 1, 1],
[1, 1, 1],
[1, 1, 0],
]
for name, matrix in [("Matrix A", matrix_a), ("Matrix B", matrix_b)]:
ones = sum(sum(row) for row in matrix)
print(name, "- ones in grid:", ones, "- expected largest area: 4")Both grids hold more ones than four. A scattered supply of ones is not a square. The ones must sit together in a solid block.
Intuition: a long run of ones is not a square
The first idea scans each row for long runs of ones. A run of five feels close to an answer. It reports the run length as a side length.
A run says nothing about the rows above or below. A square needs the same run stacked over several rows. One broken row ends the stack.
Row runs against the real answer in Matrix A
matrix_a = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0],
]
def longest_run(row):
best = run = 0
for cell in row:
run = run + 1 if cell == 1 else 0
best = max(best, run)
return best
for row in matrix_a:
print("row", row, "- longest run:", longest_run(row))
print("largest square side is only 2")A run reaches five in the third row. The rows around it break before a side of three can stack. The longest run overstates the answer by more than double.
Brute force: grow a square from every corner
The brute force treats each cell as the top left corner of a square. It grows the side one step at a time. Each growth step checks the new bottom row and the new right column.
A single zero stops the growth from that corner. The search records the largest side that stayed solid. It then moves to the next corner and starts again.
The brute force, counted
def brute_area(matrix):
rows, cols = len(matrix), len(matrix[0])
checks = 0
best = 0
for r in range(rows):
for c in range(cols):
side = 0
while r + side < rows and c + side < cols:
ok = True
for k in range(side + 1):
checks += 1
if matrix[r + side][c + k] == 0 or matrix[r + k][c + side] == 0:
ok = False
if not ok:
break
side += 1
best = max(best, side)
return best * best, checks
matrix_a = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0],
]
matrix_b = [
[0, 1, 1],
[1, 1, 1],
[1, 1, 0],
]
for name, matrix in [("Matrix A", matrix_a), ("Matrix B", matrix_b)]:
area, checks = brute_area(matrix)
print(name, "- area:", area, " cell checks:", checks)The counts stay small only because the grids are small. Every corner repeats checks that a neighbouring corner already made. That repeated work is the cost the table removes.
The optimal solution: store the side ending at each cell
The state at each cell is the side length of the largest all-ones square ending exactly at that cell. Ending means the cell is the square's bottom right corner.
A one cell extends the smallest of its three neighbours by exactly one. The neighbours are the cells above, left, and above-left. A zero cell stores zero and breaks every square through it.
The neighbour table on every case
def maximal_square(matrix):
if not matrix or not matrix[0]:
return 0, []
rows, cols = len(matrix), len(matrix[0])
table = [[0] * cols for _ in range(rows)]
best = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
if r == 0 or c == 0:
table[r][c] = 1
else:
table[r][c] = 1 + min(table[r - 1][c], table[r][c - 1], table[r - 1][c - 1])
best = max(best, table[r][c])
return best * best, table
matrix_a = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0],
]
matrix_b = [
[0, 1, 1],
[1, 1, 1],
[1, 1, 0],
]
for name, matrix, expected in [("Matrix A", matrix_a, 4), ("Matrix B", matrix_b, 4)]:
area, table = maximal_square(matrix)
print(name, "- area:", area, "expected:", expected, "match:", area == expected)Both cases pass. One weak neighbour caps the whole square. The minimum, not the maximum, is the neighbour that decides the new side.
Walkthrough: Matrix B cell by cell
The walkthrough fills the table for Matrix B. The first row and the first column can only hold squares of side one. They have no full set of neighbours.
Each later one cell reads its three stored neighbours. The smallest one sets the cap. The printed table grows one row at a time.
The side table after each row
matrix_b = [
[0, 1, 1],
[1, 1, 1],
[1, 1, 0],
]
rows, cols = len(matrix_b), len(matrix_b[0])
table = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if matrix_b[r][c] == 1:
if r == 0 or c == 0:
table[r][c] = 1
else:
table[r][c] = 1 + min(table[r - 1][c], table[r][c - 1], table[r - 1][c - 1])
print("after row", r, "table row:", table[r])
best = max(max(row) for row in table)
print("largest side:", best, "- largest area:", best * best)Two cells store the value two. One sits at the end of the second row, and the other sits in the middle of the third row. Either entry is where the area of four comes from.
Complexity
The table visits each cell once and reads three neighbours, so its time is O(rows times cols). The stored table takes O(rows times cols) space, and keeping only the largest side needs just the previous row.
The brute force regrows squares from every corner. Its check count climbs far faster than the cell count as the grid grows.
Checks against cells on all-ones grids
def brute_checks(n):
matrix = [[1] * n for _ in range(n)]
checks = 0
for r in range(n):
for c in range(n):
side = 0
while r + side < n and c + side < n:
for k in range(side + 1):
checks += 1
side += 1
return checks
for n in [2, 4, 8]:
print("grid", n, "x", n, "- brute cell checks:", brute_checks(n), " table cells:", n * n)At eight by eight the brute force makes 540 checks against 64 cells. The all-ones grid is its worst case. Every corner grows as far as the border allows.
Edge cases and pitfalls
An empty grid has no square at all. The code returns zero before reading any row. A grid of zeros also answers zero, through the table itself.
The classic pitfall reports the largest side as the answer. The problem asks for an area. The side must be squared once, at the very end.
Edge cases, run
def maximal_square(matrix):
if not matrix or not matrix[0]:
return 0, []
rows, cols = len(matrix), len(matrix[0])
table = [[0] * cols for _ in range(rows)]
best = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1:
if r == 0 or c == 0:
table[r][c] = 1
else:
table[r][c] = 1 + min(table[r - 1][c], table[r][c - 1], table[r - 1][c - 1])
best = max(best, table[r][c])
return best * best, table
print("empty grid:", maximal_square([])[0])
print("all zeros:", maximal_square([[0, 0], [0, 0]])[0])
print("single one:", maximal_square([[1]])[0])
print("single row:", maximal_square([[1, 1, 1]])[0])
print("single column:", maximal_square([[1], [1], [1]])[0])
print("solid three by three:", maximal_square([[1, 1, 1], [1, 1, 1], [1, 1, 1]])[0])The single row and single column both answer one. A line of ones is not a square of side three. Only the solid block earns the full nine.
Exercise
A one cell has neighbour sides 3 above, 1 left, and 2 above-left. What side does it store?