What is the Maximal Square Problem?
Learn the maximal square DP problem in a binary matrix, its recurrence, complexity, and how to explain it in interviews.
Expected Interview Answer
The maximal square problem finds the largest square of all 1s inside a binary matrix, solved in O(rows * cols) time by letting dp[i][j] represent the side length of the largest square whose bottom-right corner is at (i, j).
The key insight is that a square of side length k can only end at (i, j) if the cell itself is 1 and the three neighboring squares — up, left, and diagonally up-left — each support a square of at least side length k-1. This gives the recurrence dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 whenever grid[i][j] is 1, and 0 otherwise. The first row and first column are set directly from the input since they cannot support a square larger than 1. The final answer is the maximum value anywhere in the dp table, squared to get the area. As with grid path problems, the DP table can be compressed to O(cols) space using a rolling array.
- O(rows * cols) time, a single pass over the grid
- O(cols) space with a rolling array optimization
- The min-of-three-neighbors trick generalizes to maximal rectangle variants
- Avoids the O((rows*cols)^2) brute-force check of every possible square
AI Mentor Explanation
Groundstaff are checking a grid of turf patches to find the largest perfectly square section that is entirely free of bare spots, where each patch is marked usable or not. A square of a given size can only end at a patch if that patch is usable and the patch above, the patch to the left, and the patch diagonally above-left can all support a square almost that big. So the largest square ending at any patch is one more than the smallest of those three neighboring squares, but only if the current patch itself is usable. Scanning the whole grid this way finds the largest clean square instantly, without physically checking every possible square shape by hand.
Step-by-Step Explanation
Step 1
Define the state
dp[i][j] is the side length of the largest all-1s square whose bottom-right corner is at (i, j).
Step 2
Handle the base case
If grid[i][j] is 0, dp[i][j] is 0; the first row and first column equal the cell value itself.
Step 3
Apply the min-of-three recurrence
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 when grid[i][j] is 1.
Step 4
Track and square the maximum
Keep a running max side length across the whole table, then square it for the area.
What Interviewer Expects
- Explain why a min, not a max or sum, of the three neighbors is used
- Correctly identify the three relevant neighbors: top, left, top-left diagonal
- State O(rows * cols) time and mention the O(cols) space optimization
- Distinguish this from maximal rectangle, which is a harder, related problem
Common Mistakes
- Using max instead of min across the three neighbors, which overcounts invalid squares
- Forgetting the diagonal (top-left) neighbor entirely
- Returning the max dp value directly instead of squaring it for the area
- Not handling an all-zero grid, where the answer should be 0
Best Answer (HR Friendly)
“The maximal square problem is about finding the biggest square you can draw inside a grid using only cells marked as 1. I solve it by tracking, for each cell, the size of the largest square that could end there, based on the smallest of the three neighboring squares above it, to its left, and diagonally above-left, plus one.”
Code Example
def maximal_square(matrix):
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [0] * (cols + 1)
max_side = 0
prev = 0
for i in range(1, rows + 1):
prev = 0
for j in range(1, cols + 1):
temp = dp[j]
if matrix[i - 1][j - 1] == 1:
dp[j] = min(dp[j], dp[j - 1], prev) + 1
max_side = max(max_side, dp[j])
else:
dp[j] = 0
prev = temp
return max_side * max_sideFollow-up Questions
- How would you extend this to find the maximal rectangle of 1s instead of a square?
- How would you also return the coordinates of the largest square, not just its area?
- How does the diagonal neighbor prevent overcounting invalid squares?
- How would you solve this on a very wide grid streamed row by row?
MCQ Practice
1. What operation combines the three neighboring dp values in the maximal square recurrence?
The square is limited by its weakest neighbor, so the minimum of the three neighbors plus one bounds the current square size.
2. Which three neighbors does dp[i][j] depend on?
A square ending at (i, j) requires the top, left, and diagonal top-left cells to each support a square almost as large.
3. How is the final answer (area) computed from the dp table?
dp values store side lengths, so the largest square’s area is the maximum side length squared.
Flash Cards
What does dp[i][j] represent in the maximal square problem? — The side length of the largest all-1s square whose bottom-right corner is at (i, j).
What is the recurrence when grid[i][j] is 1? — dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
What is the time complexity of the DP solution? — O(rows * cols), a single pass over the grid.
How do you get the area from the dp table? — Square the maximum dp value found anywhere in the table.