Given an m x n binary matrix filled with '0's and '1's, find the largest square containing only '1's and return its area.

Examples

Example 1:

Input:
  1 0 1 0 0
  1 0 1 1 1
  1 1 1 1 1
  1 0 0 1 0

Output: 4   (a 2x2 square)

Example 2:

Input:
  0 1
  1 0

Output: 1   (a 1x1 square)

Example 3:

Input:
  0

Output: 0

Constraints

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

Thinking Process

The DP Definition

Define dp[i][j] = side length of the largest square whose bottom-right corner is at (i, j).

The Transition

A square at (i, j) can only be as large as the smallest of its three neighbors plus one:

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Why? A square of side k at (i, j) requires:

  • A square of side k-1 ending at (i-1, j) (top)
  • A square of side k-1 ending at (i, j-1) (left)
  • A square of side k-1 ending at (i-1, j-1) (diagonal)

If any of these is smaller, it becomes the bottleneck.

  ┌──────────┐
  │ diag  top│
  │ left  cur│
  └──────────┘

dp[i-1][j-1]  dp[i-1][j]
dp[i][j-1]    dp[i][j] = 1 + min(top, left, diag)

Complete Walk-through

Matrix:                    DP table:
1 0 1 0 0                 1 0 1 0 0
1 0 1 1 1                 1 0 1 1 1
1 1 1 1 1                 1 1 1 2 2
1 0 0 1 0                 1 0 0 1 0

Key cells:

  • dp[2][3]: min(top=1, left=1, diag=1) + 1 = 2 – a 2x2 square forms
  • dp[2][4]: min(top=1, left=2, diag=1) + 1 = 2 – another 2x2 square
  • dp[3][3]: min(top=2, left=0, diag=1) + 1 = 1 – left is 0, so only 1x1

Max value = 2, so answer = 2^2 = 4.

1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

from typing import List


class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * cols for _ in range(rows)]
        max_side = 0

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = 1 + min(
                            dp[i - 1][j],
                            dp[i][j - 1],
                            dp[i - 1][j - 1],
                        )
                    max_side = max(max_side, dp[i][j])
        return max_side * max_side

Solution Explanation

Approach: 1D DP (this problem)

Key idea: ### The DP Definition

How the code works:

  • A square of side k-1 ending at (i-1, j) (top)
  • A square of side k-1 ending at (i, j-1) (left)
  • A square of side k-1 ending at (i-1, j-1) (diagonal)
  • dp[2][3]: min(top=1, left=1, diag=1) + 1 = 2 – a 2x2 square forms
  • dp[2][4]: min(top=1, left=2, diag=1) + 1 = 2 – another 2x2 square
  • dp[3][3]: min(top=2, left=0, diag=1) + 1 = 1 – left is 0, so only 1x1

Walkthrough — input 1 0 1 0 0, expected output 4 (a 2x2 square):

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  • Returning maxSide instead of maxSide * maxSide: The problem asks for area, not side length
  • Treating matrix[i][j] as int: The matrix contains char values ('0'/'1'), not integers
  • Forgetting to reset dp[j] = 0 in 1D version: When matrix[i][j] == '0', the cell must be explicitly zeroed

Key Takeaways

  • Classic 2D DP pattern: define state at each cell, derive from neighbors
  • The min of three neighbors is the core insight – a square is only as large as its weakest constraint
  • Space optimization from 2D to 1D is a standard technique: save the diagonal before overwriting
  • Answer is text{maxSide}^2 (area, not side length)

References

Template Reference