Maximal Square — InterviewPrepKit

Solving tips

Reframe globally-to-locally: dp[i][j] = side of the largest all-ones square whose BOTTOM-RIGHT corner is (i,j); the answer is (max side)^2.
Recurrence for a '1' cell: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); it must be min (the square is limited by its weakest supporting neighbor), not max.
Return the AREA (square the best side), not the side itself; and compare cells against the string '1'/'0', not integers.
Target O(m*n) time, O(n) space with one rolling row plus a saved diag scalar for the overwritten top-left value.

Problem

Given an m x n binary matrix filled with characters '0' and '1', find the largest square made up entirely of '1's and return its area.

If the matrix contains no '1', return 0.

Examples

[["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]] → 4 — a 2×2 block of ones (side 2, area 2² = 4) sits in the middle.
[["0","1"], ["1","0"]] → 1 — no 2×2 all-ones block exists, so the best is a single 1 (area 1).
[["0"]] → 0 — no ones at all.

Constraints

m == matrix.length, n == matrix[0].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

Checking every possible square explicitly is far too slow at 300×300; the expected solution is O(m × n).

Think about it first

Hint 1

Instead of asking "where is the biggest square," ask a local question at each cell: "what is the largest all-ones square whose **bottom-right corner** is exactly here?" The global answer is the biggest of those.

Hint 2

A cell can be the bottom-right corner of a side-`k` square only if the cells directly above, directly left, and diagonally up-left can all support a side-`(k-1)` square. That ties `dp[i][j]` to three neighbors — a 2-D DP.

Hint 3

If `matrix[i][j] == '1'`: `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`; otherwise `dp[i][j] = 0`. Track the maximum side seen; the answer is that side squared.

TL;DR

DP where dp[i][j] = side of the largest all-ones square ending at (i, j) — O(m × n) time, O(n) space after rolling to one row.

Approach 1 — Brute force

Intuition: treat each '1' cell as a possible top-left corner and grow the square side by side, checking that each new bottom row and right column is all ones, until it fails or runs off the matrix.

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        best = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != "1":
                    continue
                side = 1
                while i + side < m and j + side < n:
                    ok = True
                    for c in range(j, j + side + 1):        # new bottom row
                        if matrix[i + side][c] != "1":
                            ok = False
                            break
                    for r in range(i, i + side + 1):        # new right column
                        if matrix[r][j + side] != "1":
                            ok = False
                            break
                    if not ok:
                        break
                    side += 1
                best = max(best, side)
        return best * best

Complexity: O(m · n · min(m, n)) time, O(1) extra space.

Why the constraints kill it: at 300×300 with a mostly-ones matrix this approaches ~2.7×10^7 border checks per growth level across all cells — much slower than the linear DP, and it degrades on dense inputs.

Approach 2 — Top-down memoization

The insight: define side(i, j) = the side of the largest all-ones square whose bottom-right corner is (i, j). A cell can anchor a side-k square only if its top, left, and top-left neighbors each anchor a side-(k-1) square — so side(i, j) = 1 + min of those three. Cache each (i, j).

from functools import lru_cache


class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])

        @lru_cache(maxsize=None)
        def side(i: int, j: int) -> int:
            if i < 0 or j < 0 or matrix[i][j] != "1":
                return 0
            return 1 + min(side(i - 1, j), side(i, j - 1), side(i - 1, j - 1))

        best = 0
        for i in range(m):
            for j in range(n):
                best = max(best, side(i, j))
        return best * best

Complexity: O(m × n) time and space.

Approach 3 — Bottom-up 2-D table

Table meaning: dp[i][j] = side length of the largest all-ones square whose bottom-right corner is (i, j).

2-D recurrence:

dp[i][j] = 0                                             if matrix[i][j] == '0'
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if matrix[i][j] == '1'

A padded first row and column of zeros handle the borders. The answer is (max dp)².

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        best = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == "1":
                    dp[i][j] = 1 + min(dp[i - 1][j],
                                       dp[i][j - 1],
                                       dp[i - 1][j - 1])
                    best = max(best, dp[i][j])
        return best * best

Walkthrough on the first example. The two interior rows/columns of ones produce a dp value of 2 at the cell where a full 2×2 block closes (its top, left, and top-left neighbors all hold 1). No cell reaches 3 because no 3×3 all-ones block exists. best = 2, area 2² = 4.

Complexity: O(m × n) time, O(m × n) space.

Approach 4 — Space-optimized rolling row

The insight: dp[i][j] reads the previous row (dp[i-1][j], dp[i-1][j-1]) and the current row’s left neighbor (dp[i][j-1]). Keep one row and a single diag scalar for the top-left value that would otherwise be overwritten.

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        best = 0
        for i in range(1, m + 1):
            diag = 0                                 # dp[i-1][j-1]
            for j in range(1, n + 1):
                temp = dp[j]                         # save dp[i-1][j] before overwrite
                if matrix[i - 1][j - 1] == "1":
                    dp[j] = 1 + min(dp[j], dp[j - 1], diag)
                    best = max(best, dp[j])
                else:
                    dp[j] = 0
                diag = temp
            dp[0] = 0                                # left border stays 0 for next row
        return best * best

Complexity: O(m × n) time, O(n) space.

Common pitfalls

Returning the side instead of the area — the problem wants area, so square the best side.
Using min vs max — the square is limited by its weakest supporting neighbor, so it must be min of the three; max overcounts and reports squares that aren’t solid.
String vs int cells — the matrix holds '1'/'0' characters; compare against the strings (or convert), don’t treat them as integers.
In the rolled version, forgetting to snapshot diag (the old top-left) before overwriting dp[j] corrupts the diagonal term.

Pattern takeaway

“Largest shape ending here” is a powerful 2-D DP reframing: instead of searching over all shapes, define each cell as the best structure it can close, built from its neighbors. The min-of-three-neighbors-plus-one recurrence is the signature of square/rectangle problems where every sub-square of a valid square must also be valid.