Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Maximal Square
• Main tags: Array, Dynamic Programming, Matrix

What the problem is really asking

The input is a grid of "0" and "1" values. The job is to find the area of the largest square made entirely of 1s.

The part that usually traps people is the word “square.” A brute-force approach tends to ask:

• pick a cell
• try every possible square size starting there
• keep checking whether every cell on the border or inside is still 1

That works, but it does far too much repeated work.

The better question is:

“If this cell is the bottom-right corner of a valid all-ones square, how large can that square be?”

Once the problem is framed that way, the solution becomes a local dynamic programming recurrence instead of a global search.

The key dynamic programming insight

Define dp[row][col] as:

the side length of the largest all-ones square whose bottom-right corner is at matrix[row][col].

That definition is useful because a square can only grow by one if three smaller squares already support it:

• the square ending directly above
• the square ending directly to the left
• the square ending diagonally up-left

If the current cell is "0", then no all-ones square can end here, so the value is 0.

If the current cell is "1", then:

dp[row][col] = 1 + min(top, left, top_left)

Why the min?

Because a larger square is only possible when all three neighboring directions can support it. If even one of them is smaller, that smaller one becomes the bottleneck. A square of side k needs k - 1 valid support in every relevant direction.

How to derive the recurrence

Suppose the current cell contains "1".

If this cell is going to finish a square of side 3, then:

• the cells above it must be able to finish a square of at least side 2
• the cells to the left must be able to finish a square of at least side 2
• the diagonal up-left region must also support side 2

If any one of those three only supports side 1, then the current cell cannot complete a side-3 square. It can only grow to side 2.

That is exactly why the recurrence takes the minimum of those three neighboring states.

This is a strong interview derivation because it shows the recurrence is not magic. It comes directly from the geometry of how a square expands.

Two good solution forms

There are two standard ways to implement this idea:

• a full O(rows * cols) DP table, which is simplest to explain
• a rolling O(cols) DP array, which keeps the same runtime and reduces memory

The Python solution below uses the space-optimized version, since it is still readable and is the best practical implementation.

A small example

For this matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 1 1 1

Look at the bottom-right cell of the 2 x 2 square in the lower-right area. That cell can only form a larger square if:

• the cell above already ends a valid square
• the cell to the left already ends a valid square
• the up-left diagonal cell also ends a valid square

When all three are at least 1, the current cell can grow that region to side 2. Repeating that idea across the grid finds the largest square automatically.

Python solution

from typing import List, Sequence


BinaryMatrix = Sequence[Sequence[str]]


def largest_square_side(binary_matrix: BinaryMatrix) -> int:
    """
    Return the side length of the largest all-ones square.

    The algorithm uses a rolling DP array where dp[c] represents the largest
    square side ending at the current row and column c - 1 after the update.
    """
    if not binary_matrix or not binary_matrix[0]:
        return 0

    column_count = len(binary_matrix[0])

    for row in binary_matrix:
        if len(row) != column_count:
            raise ValueError("binary_matrix must be rectangular")

    dp_by_column = [0] * (column_count + 1)
    best_side_length = 0

    for row in binary_matrix:
        previous_diagonal = 0

        for column_index in range(1, column_count + 1):
            top = dp_by_column[column_index]
            left = dp_by_column[column_index - 1]

            if row[column_index - 1] == "1":
                # A larger square can grow here only if top, left, and the
                # previous row's previous column can all support it.
                dp_by_column[column_index] = 1 + min(
                    top,
                    left,
                    previous_diagonal,
                )

                if dp_by_column[column_index] > best_side_length:
                    best_side_length = dp_by_column[column_index]
            else:
                dp_by_column[column_index] = 0

            # Preserve the old top value before the next iteration overwrites it.
            previous_diagonal = top

    return best_side_length


def maximal_square_area(binary_matrix: BinaryMatrix) -> int:
    """
    Return the area of the largest all-ones square.
    """
    side_length = largest_square_side(binary_matrix)
    return side_length * side_length


class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        return maximal_square_area(matrix)

Why this works

The invariant is:

after processing a cell, the DP state at that position stores the side length of the largest all-ones square ending exactly there.

That statement is clearly true for any cell containing "0", because the value must be 0.

For a cell containing "1", any square ending there must extend from the top, left, and top-left neighbors. The largest valid extension is therefore constrained by the smallest of those three values. Adding 1 for the current cell gives the correct side length for the square ending here.

Taking the maximum side length over the whole scan finds the globally largest square. Squaring that side length produces the area LeetCode asks for.

The runtime is O(rows * cols) because every cell is processed once. The extra space is O(cols) because the implementation keeps only one rolling row of DP state.

Interview follow-ups

Can you write the simpler full-table version first?

Yes. The cleanest derivation usually starts with a full 2D table where dp[row][col] directly stores the largest square side ending at that cell. The transition is exactly the same: 1 + min(top, left, top_left) when the current cell is "1", otherwise 0. That version is often the best one to explain first because it mirrors the recurrence almost line for line. Its tradeoff is space: it uses O(rows * cols) extra memory instead of O(cols), while keeping the same O(rows * cols) runtime.

Can you return the coordinates of the largest square, not just its area?

Yes. While computing DP, keep track of the best side length seen so far and the bottom-right coordinate where it occurs. Once the scan finishes, the top-left corner is easy to reconstruct: if the best square has side k and ends at (row, col), then its top-left corner is (row - k + 1, col - k + 1). The recurrence and correctness argument do not change. The complexity stays O(rows * cols) time, and the extra memory is still O(cols) if the rolling-array version is used.

How would you count all all-ones squares instead of only the largest one?

That is a common extension, and the same DP table solves it. Each DP value already tells how many square sizes end at that cell. For example, if dp[row][col] = 3, then that cell is the bottom-right corner of a 1 x 1, 2 x 2, and 3 x 3 all-ones square. So instead of tracking only the maximum, sum all DP values across the grid. The runtime stays O(rows * cols). The tradeoff is conceptual rather than performance-related: the recurrence is the same, but the output interpretation changes from “largest side” to “total number of valid squares.”

What if the interviewer changes the problem to largest rectangle of ones?

That becomes a different problem with a different optimal pattern. The standard approach is to treat each row as the base of a histogram: accumulate consecutive 1 heights column by column, then solve Largest Rectangle in Histogram for each row with a monotonic stack. That also runs in O(rows * cols) time, but the reasoning changes completely because rectangles do not have the same local min(top, left, top_left) structure that makes the square DP work. This is a useful contrast to mention in an interview because it shows the candidate understands why the square recurrence is specific to squares.

Practical takeaway

The fastest way to recognize this problem is to stop thinking about checking full squares directly.

Think cell-by-cell and ask:

“If this cell is the bottom-right corner, how large a square can end here?”

That leads naturally to the min(top, left, top_left) + 1 recurrence, which gives the optimal solution in one grid scan.