Skip to content

221. Maximal Square

On LeetCode ->

Problem

Given a binary matrix, return the area of its largest square containing only "1" cells.

matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]
largest side = 2
output = 4

Key trick

Let dp[c] be the side length of the largest all-ones square ending at the current cell. A "1" extends the smallest square supported by its top, left, and top-left neighbors.

Trap

  • Checking only whether the largest top-left square can be extended misses smaller valid squares.
  • The result is the square's area, so return best * best.
  • Reset the DP state to zero when the current cell is "0".

Why is it interesting?

It turns a geometric constraint into a local recurrence and demonstrates how a 2D DP can be compressed to one row.

Python solution

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        n = len(matrix[0])
        dp = [0] * (n + 1)
        best = 0

        for row in matrix:
            diag = 0
            for c in range(1, n + 1):
                top = dp[c]
                if row[c - 1] == "1":
                    # A larger square requires support from all three neighbors.
                    dp[c] = 1 + min(top, dp[c - 1], diag)
                    best = max(best, dp[c])
                else:
                    dp[c] = 0
                # Preserve the old top value as the next cell's top-left value.
                diag = top
        return best * best

Time complexity: \(O(mn)\).

Space complexity: \(O(n)\).

Comment on my solution

Your DP meaning is appropriate, but the transition only tries to extend the entire square at the top-left neighbor. If that extension fails, the current cell may still end a smaller square larger than 1, which must be recorded for later cells.

In the failing case, this causes dp[3][2] to remain 1 even though it should be 2, preventing the final 3 x 3 square from being discovered. Taking the minimum of the top, left, and top-left states handles every possible smaller square directly. Your repeated row and column scans also increase the worst-case time complexity beyond \(O(mn)\).

# ideas:
# - 2D DP
#   - dp[r][c] = width of the filled square with bottom right cell (r, c)
#   - DP transition: if dp[r - 1][c - 1] != 0, let call width this number,
#     check if (r, c - width) -> (r, c) and (r - width, c) -> (r, c) only
#     1.  If True, set dp[r][c] = width + 1 and update best area


# Wrong Answer: 77/81 testcases passed
# [["0","0","0","1"],
#  ["1","1","0","1"],
#  ["1","1","1","1"],
#  ["0","1","1","1"],
#  ["0","1","1","1"]]
# Output: 4
# Expected: 9
class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        best = int(any(matrix[r][c] == "1" for r in range(m) for c in range(n)))
        dp = [[int(row[c]) for c in range(n)] for row in matrix]
        for r in range(1, m):
            for c in range(1, n):
                width = dp[r - 1][c - 1]
                if matrix[r][c] == "1" and width:
                    if (all(dp[r][c - width : c + 1]) and all(dp[i][c] for i in range(r - width, r + 1))):
                        width += 1
                        area = width * width
                        best = max(best, area)
                        dp[r][c] = width
        return best