Domain 2MediumCORE

Maximal Square

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

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"). Dimensions m, n.
  • Output: An integer representing the area (side×sideside \times side).

Constraints & Edge Cases:

  • Matrix dimensions are between 1 and 300. This allows for O(m⋅n)O(m \cdot n) time complexity solutions without timeout issues.
  • The matrix elements are characters, not integers (e.g., "1" vs 1). 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.

Intuition

Initially, one might consider a brute-force approach: iterate through every possible top-left corner (i,j)(i, j) and try to expand the square size kk 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 (O(m⋅n3)O(m \cdot n^3) or similar), which will TLE (Time Limit Exceeded) on larger inputs like m=n=50m=n=50.

The key insight for optimization is Dynamic Programming. We can determine the size of a square ending at position (i,j)(i, j) 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 k+1k+1 ending at (i,j)(i, j), we need squares of size kk 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: dp[i][j]=min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

If matrix[i][j] is '0', then dp[i][j]dp[i][j] 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.

  1. Initialization: Create a dp table 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.
  2. Iteration: Loop i from 0 to m-1, and j from 0 to n-1.
  3. State Transition:
    • If the current cell is '0': Set dp[i][j]=0dp[i][j] = 0.
    • If the current cell is '1': Check neighbors (i, j-1), (i-1, j), and (i-1, j-1) (handling boundary conditions where i=0 or j=0). Set dp[i][j]dp[i][j] to min⁡(neighbors)+1\min(\text{neighbors}) + 1.
  4. Tracking Max: Maintain a variable max_side updated whenever we find a larger value in the DP table.
  5. Result: Return max_side * max_side.

Complexity Analysis

  • Time Complexity: O(m⋅n)O(m \cdot n). 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: O(m⋅n)O(m \cdot n) for the DP table. This can be optimized to O(n)O(n) 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_side remains 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 min(0,0,0)+1=1min(0,0,0)+1 = 1. Returns 12=11^2=1. Correct.
  • Single Row/Column: Boundary logic (if i > 0 etc.) ensures we don’t access invalid indices when the loop is on the first row or column.