221. Maximal Square
Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 39.6%
Problem Breakdown
We are given an m x n binary matrix where each cell contains either '0' or '1'. The goal is to find the area of the largest square subgrid that consists entirely of '1's and return that integer value.
Key Inputs & Outputs:
- Input: A 2D list (matrix) containing strings (
"0"/"1"). Dimensionsm,n. - Output: An integer representing the area ().
Constraints & Edge Cases:
- Matrix dimensions are between 1 and 300. This allows for time complexity solutions without timeout issues.
- The matrix elements are characters, not integers (e.g.,
"1"vs1). We must handle string comparison carefully. - Implicit Edge Cases:
- A row or column full of
'0's will naturally result in a side length of 0 for that region. - If the matrix contains only
'0', the max area is 0. - Single cell matrices (1x1) must be handled correctly without index out-of-bounds errors during neighbor checks.
- A row or column full of
Intuition
Initially, one might consider a brute-force approach: iterate through every possible top-left corner and try to expand the square size until we hit a '0'. However, checking if a specific subgrid is all '1's takes time proportional to its area. Summing this up over all squares leads to roughly cubic complexity relative to grid dimensions ( or similar), which will TLE (Time Limit Exceeded) on larger inputs like .
The key insight for optimization is Dynamic Programming. We can determine the size of a square ending at position based on its neighbors. If matrix[i][j] is '1', it cannot be part of any valid square if any of its immediate top-left, left, or top neighbors are not capable of supporting that same side length.
Specifically:
To form a square of size ending at , we need squares of size to exist in the cell directly above it (i-1, j), the cell directly left (i, j-1), and diagonally top-left (i-1, j-1). The bottleneck is determined by the smallest square among these three neighbors. Thus:
If matrix[i][j] is '0', then must be 0 because no square can end there. We track the maximum value in our DP table and return its square at the end.
Approach
We will use a standard Dynamic Programming approach with an auxiliary matrix to store side lengths of squares ending at each cell.
- Initialization: Create a
dptable of size(m+1) x (n+1)initialized to zeros. We add padding rows/cols or handle boundary checks explicitly; handling boundaries inside the loop is cleaner for memory but requires index guards. For clarity in explanation, I will iterate through valid indices and check if neighbors exist. - Iteration: Loop
ifrom 0 tom-1, andjfrom 0 ton-1. - State Transition:
- If the current cell is
'0': Set . - If the current cell is
'1': Check neighbors(i, j-1),(i-1, j), and(i-1, j-1)(handling boundary conditions wherei=0orj=0). Set to .
- If the current cell is
- Tracking Max: Maintain a variable
max_sideupdated whenever we find a larger value in the DP table. - Result: Return
max_side * max_side.
Complexity Analysis
- Time Complexity: . We visit each cell exactly once, performing constant-time operations (comparisons and min calculations). With constraints up to 300x300, this is roughly 90,000 iterations.
- Space Complexity: for the DP table. This can be optimized to by only storing the previous row’s values during iteration (since we only need
dp[i-1][...]and current updates), but given the constraints, a full 2D array is acceptable and easier to reason about in an interview setting unless memory optimization is explicitly requested.
Solution
def maximalSquare(matrix):
if not matrix or not matrix[0]:
return 0
m = len(matrix)
n = len(matrix[0])
# dp[i][j] will store the side length of the largest square
# whose bottom-right corner is at (i, j).
# We use a separate DP table to avoid modifying input.
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
# Handle boundary conditions:
# If on first row or column, neighbors don't exist (conceptually size is just current cell)
# We can treat non-existent neighbors as 0.
top = dp[i-1][j] if i > 0 else 0
left = dp[i][j-1] if j > 0 else 0
diag_top_left = dp[i-1][j-1] if (i > 0 and j > 0) else 0
# The size is limited by the smallest neighbor + current cell itself
side_len = min(top, left, diag_top_left) + 1
dp[i][j] = side_len
max_side = max(max_side, side_len)
else:
dp[i][j] = 0
return max_side * max_side
Edge Cases Handled
- Empty Matrix: The code checks
if not matrix or not matrix[0]:at the start to handle empty inputs gracefully (returning 0), though constraints guarantee non-empty. - All ‘0’s: If no
'1'is found,max_sideremains 0, returning area 0 correctly. - Single Element Matrix (
[[ "1" ]]): The loop runs once for(0,0). Neighbors are treated as 0 (via boundary checks). Logic sets side to . Returns . Correct. - Single Row/Column: Boundary logic (
if i > 0etc.) ensures we don’t access invalid indices when the loop is on the first row or column.