{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Maximal Square – Solution & Complexity

Interview solutions
/
Maximal Square

Solution Walkthrough

  1. Step 1: Start from what makes a square valid

    • A square is only valid if every cell inside it is 1.
    • The answer asks for area, but it is easier to reason about side length first and square it at the end.
    • That leads naturally to either expanding candidate squares or building a DP table of best side lengths.

  2. Step 2: Brute force: expand from each top-left 1

    • Treat each cell containing 1 as a possible top-left corner.
    • Try to grow the square one layer at a time, checking the newly added bottom row and right column before accepting the larger side length.
    • This works, but in the worst case it repeatedly rechecks many cells and costs O(m*n*k^2) time where k = min(m, n).
    def maximal_square(matrix: list[list[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    best = 0

    def can_expand(top: int, left: int, side: int) -> bool:
        bottom = top + side
        right = left + side

        for col in range(left, right + 1):
            if matrix[bottom][col] == 0:
                return False

        for row in range(top, bottom):
            if matrix[row][right] == 0:
                return False

        return True

    for top in range(rows):
        for left in range(cols):
            if matrix[top][left] == 0:
                continue

            side = 1
            best = max(best, side)

            while top + side < rows and left + side < cols and can_expand(top, left, side):
                side += 1
                best = max(best, side)

    return best * best

  3. Step 3: Use DP for squares ending at each cell

    • Let dp[r][c] be the side length of the largest all-1 square whose bottom-right corner is (r, c).
    • If matrix[r][c] is 0, then dp[r][c] = 0.
    • Otherwise, border cells can only form a 1x1 square, and interior cells extend the smallest of the three neighboring squares: top, left, and top-left diagonal.

  4. Step 4: Optimal solution: dynamic programming in one pass

    • Sweep the matrix row by row.
    • When matrix[r][c] == 1, compute dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) for interior cells, or 1 on the first row/column.
    • Track the largest side length seen, then return its square as the area. This runs in O(m*n) time and O(m*n) space.
    def maximal_square(matrix: list[list[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]
    max_side = 0

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 0:
                continue

            if row == 0 or col == 0:
                dp[row][col] = 1
            else:
                dp[row][col] = min(
                    dp[row - 1][col],
                    dp[row][col - 1],
                    dp[row - 1][col - 1],
                ) + 1

            max_side = max(max_side, dp[row][col])

    return max_side * max_side

FAQ

See also

Practice Maximal Square online (run code in the browser)Longest Increasing Path in a Matrix solution (hard)Unique Paths II solution (medium)01 Matrix solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?