Maximal Square

A square is global shape, but its growth has a local rule. Writing the direct growth check first makes that rule easier to trust.

Let the matrix have m rows and n columns, and let k = min(m, n).

Grow every square

Treat every cell as a possible top-left corner. Grow the side one step at a time. The smaller square was already verified, so each growth checks only its new bottom row and right column. Once a border contains "0", every larger square from that corner contains the same zero and can be abandoned.

def maximal_square(matrix: list[list[str]]) -> int:
    rows, cols = len(matrix), len(matrix[0])
    best_area = 0
 
    for top in range(rows):
        for left in range(cols):
            limit = min(rows - top, cols - left)
            for side in range(1, limit + 1):
                bottom = top + side - 1
                right = left + side - 1
 
                bottom_clear = all(
                    matrix[bottom][col] == "1"
                    for col in range(left, right + 1)
                )
                right_clear = all(
                    matrix[row][right] == "1"
                    for row in range(top, bottom)
                )
                if not bottom_clear or not right_clear:
                    break
 
                best_area = max(best_area, side * side)
 
    return best_area

Time O(mn · k²) in the worst case: each corner tries k sides whose new borders cost up to k to inspect. Space O(1) beyond loop variables.

Largest-side DP

Define the DP state dp[r][c] as the side length of the largest all-ones square whose bottom-right corner is (r, c). This is bottom-up dynamic programming (DP).

When a cell is "0", its state is zero. When it's "1", the square can extend only as far as all three supporting neighbors:

dp[r][c] = 1 + min(up, left, upper-left).

Only the previous row and the current row are needed. The variable diagonal saves the old upper-left value before the row is overwritten.

def maximal_square(matrix: list[list[str]]) -> int:
    cols = len(matrix[0])
    dp = [0] * (cols + 1)
    best_side = 0
 
    for row in matrix:
        diagonal = 0
        for col in range(1, cols + 1):
            up = dp[col]
            if row[col - 1] == "1":
                dp[col] = 1 + min(up, dp[col - 1], diagonal)
                best_side = max(best_side, dp[col])
            else:
                dp[col] = 0
            diagonal = up
 
    return best_side * best_side

Time O(mn) because each cell is processed once. Space O(n) for the rolling DP row.

Tracking the side length keeps the recurrence local; squaring only once at the return keeps area out of the state entirely.