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

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();

        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        int maxSide = 0;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || 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]
                        });
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};

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