Problem Description

You are given a 2D binary matrix of size m x n where each cell contains either '0' or '1'. Your task is to find the largest square that contains only '1's and return its area.

A square in the matrix means a region where all cells form a perfect square shape (equal width and height) and every cell within that square contains '1'.

For example, if you find a square with side length 3, it would be a 3x3 region where all 9 cells contain '1'. The area of this square would be 3 × 3 = 9.

The challenge is to identify the maximum possible square that can be formed using only cells containing '1' and calculate its area. If no square of '1's exists (all cells are '0' or only isolated '1's exist), the answer would be 0.

The solution uses dynamic programming where dp[i+1][j+1] represents the side length of the largest square whose bottom-right corner is at position (i, j) in the original matrix. The key insight is that the side length of a square at position (i, j) depends on the minimum of three adjacent squares: the one directly above, the one to the left, and the one diagonally above-left, plus 1 if the current cell is '1'.

The state transition formula is:

• If matrix[i][j] = '0', then dp[i+1][j+1] = 0
• If matrix[i][j] = '1', then dp[i+1][j+1] = min(dp[i][j], dp[i][j+1], dp[i+1][j]) + 1

The final answer is the square of the maximum side length found, which gives us the area.

Intuition

The key observation is that any square can be built by extending a smaller square. If we're standing at a cell with value '1', we can ask: "What's the largest square I can form with this cell as the bottom-right corner?"

To form a square of side length k at position (i, j), three conditions must be met:

1. There must be a square of side length k-1 ending at position (i-1, j-1) (diagonally up-left)
2. There must be at least k-1 consecutive '1's above (ending at position (i-1, j))
3. There must be at least k-1 consecutive '1's to the left (ending at position (i, j-1))

Think of it like building blocks - to add one more layer to form a bigger square, you need the foundation from three directions: top, left, and top-left diagonal.

The brilliant insight is that we don't need to track "consecutive '1's" separately. If we know the maximum square side length ending at each of these three positions, the minimum among them tells us the constraint. Why the minimum? Because the smallest value limits how much we can extend. If the top has a square of side 3, left has side 2, and diagonal has side 4, we can only extend by the minimum (2) plus our current cell, giving us a square of side 3.

This naturally leads to the recurrence relation: dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1 when matrix[i][j] = '1'.

By processing each cell and keeping track of the maximum square side length found, we can compute the final area by squaring this maximum value.

Solution Approach

We implement the solution using dynamic programming with a 2D DP table. Here's the step-by-step implementation:

1. Initialize the DP Table: Create a 2D array dp of size (m+1) × (n+1) where m and n are the dimensions of the input matrix. The extra row and column (filled with zeros) serve as padding to handle boundary cases elegantly without additional conditional checks.

dp = [[0] * (n + 1) for _ in range(m + 1)]

2. Track Maximum Square Side Length: Initialize a variable mx = 0 to keep track of the maximum square side length encountered during processing.

3. Iterate Through the Matrix: For each cell (i, j) in the original matrix:

• Check if matrix[i][j] == '1'
• If it is '1', apply the state transition equation
• Update the maximum side length

4. Apply the State Transition: The core logic uses the recurrence relation:

This formula means:

• dp[i][j]: Side length of square ending at diagonal position
• dp[i][j + 1]: Side length of square ending at position above
• dp[i + 1][j]: Side length of square ending at position to the left
• Take the minimum of these three values and add 1

5. Update Maximum: After calculating dp[i + 1][j + 1], update the maximum side length:

mx = max(mx, dp[i + 1][j + 1])

6. Return the Area: Since mx stores the maximum side length, the area of the largest square is mx * mx.

Time Complexity: O(m × n) - We visit each cell once
Space Complexity: O(m × n) - For the DP table

The elegance of this solution lies in how the padding eliminates boundary checks and how the recurrence relation captures the constraint that all three adjacent regions must support the square extension.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 4×3 matrix:

1 0 1
1 1 1
1 1 0

We'll create a DP table of size 5×4 (with padding):

Initial DP table (all zeros):

    j: 0  1  2  3
i:0    0  0  0  0
  1    0  0  0  0
  2    0  0  0  0
  3    0  0  0  0
  4    0  0  0  0

Processing each cell:

Cell (0,0) - matrix value '1':

• dp[1][1] = min(dp[0][0], dp[0][1], dp[1][0]) + 1 = min(0,0,0) + 1 = 1
• mx = 1

Cell (0,1) - matrix value '0':

• dp[1][2] = 0 (since matrix[0][1] = '0')

Cell (0,2) - matrix value '1':

• dp[1][3] = min(dp[0][2], dp[0][3], dp[1][2]) + 1 = min(0,0,0) + 1 = 1

After row 0:

    j: 0  1  2  3
i:0    0  0  0  0
  1    0  1  0  1
  2    0  0  0  0
  3    0  0  0  0
  4    0  0  0  0

Cell (1,0) - matrix value '1':

• dp[2][1] = min(dp[1][0], dp[1][1], dp[2][0]) + 1 = min(0,1,0) + 1 = 1

Cell (1,1) - matrix value '1':

• dp[2][2] = min(dp[1][1], dp[1][2], dp[2][1]) + 1 = min(1,0,1) + 1 = 1

Cell (1,2) - matrix value '1':

• dp[2][3] = min(dp[1][2], dp[1][3], dp[2][2]) + 1 = min(0,1,1) + 1 = 1

After row 1:

    j: 0  1  2  3
i:0    0  0  0  0
  1    0  1  0  1
  2    0  1  1  1
  3    0  0  0  0
  4    0  0  0  0

Cell (2,0) - matrix value '1':

• dp[3][1] = min(dp[2][0], dp[2][1], dp[3][0]) + 1 = min(0,1,0) + 1 = 1

Cell (2,1) - matrix value '1':

• dp[3][2] = min(dp[2][1], dp[2][2], dp[3][1]) + 1 = min(1,1,1) + 1 = 2
• mx = 2 (updated!)

This is the key moment! At position (2,1), we can form a 2×2 square because:

• There's a 1×1 square ending at (1,0) - shown by dp[2][1] = 1
• There's a 1×1 square ending at (1,1) - shown by dp[2][2] = 1
• There's a 1×1 square ending at (0,0) - shown by dp[1][1] = 1
• Current cell is '1'

Cell (2,2) - matrix value '0':

• dp[3][3] = 0 (since matrix[2][2] = '0')

Final DP table:

    j: 0  1  2  3
i:0    0  0  0  0
  1    0  1  0  1
  2    0  1  1  1
  3    0  1  2  0
  4    0  0  0  0

Result:

• Maximum side length found: mx = 2
• Area of largest square: 2 × 2 = 4

The 2×2 square is formed by cells at positions (1,0), (1,1), (2,0), and (2,1) in the original matrix.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses nested loops to iterate through each cell of the matrix exactly once. The outer loop runs m times (number of rows), and the inner loop runs n times (number of columns) for each iteration of the outer loop. Within each iteration, the operations performed (checking if the cell is '1', calculating the minimum of three values, and updating the maximum) are all constant time O(1) operations. Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The algorithm creates a 2D DP table dp with dimensions (m + 1) × (n + 1) to store the side length of the largest square ending at each position. This requires O((m + 1) × (n + 1)) space, which simplifies to O(m × n). The additional variables mx, i, and j use constant space O(1). Therefore, the overall space complexity is O(m × n).

Where m and n are the number of rows and columns of the matrix, respectively.

Common Pitfalls

1. Confusing Side Length with Area

One of the most frequent mistakes is returning the side length instead of the area. The DP table stores the side length of the largest square, but the problem asks for the area.

Incorrect:

return max_side_length  # Returns side length, not area!

Correct:

return max_side_length * max_side_length  # Returns area

2. Index Confusion with Padding

The DP table has dimensions (m+1) × (n+1) while the original matrix is m × n. This offset can lead to indexing errors when accessing elements.

Incorrect:

# Forgetting the offset when updating dp
if matrix[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  # Wrong indices!

Correct:

# Properly offsetting indices by 1
if matrix[i][j] == '1':
    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1

3. String vs Integer Comparison

The matrix contains string characters '0' and '1', not integers. Comparing with integer values will always return False.

Incorrect:

if matrix[i][j] == 1:  # Comparing string with integer
    # This condition will never be True

Correct:

if matrix[i][j] == '1':  # Comparing string with string
    # Works correctly

4. Not Handling Edge Cases

Failing to handle empty matrices or matrices with single row/column can cause index out of bounds errors.

Solution:

def maximalSquare(self, matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:  # Handle empty matrix
        return 0
  
    rows, cols = len(matrix), len(matrix[0])
    # Continue with normal logic...

5. Incorrect Order in min() Function

While the order doesn't affect correctness for the min function, maintaining consistency with the conceptual model (top, left, diagonal) helps avoid confusion.

Better Practice:

dp[i+1][j+1] = min(
    dp[i][j+1],    # Top
    dp[i+1][j],    # Left
    dp[i][j]       # Diagonal
) + 1

6. Space Optimization Pitfall

When optimizing space to use only two rows instead of the full DP table, a common mistake is overwriting values before they're used.

Incorrect Space-Optimized Version:

# Using single row - loses diagonal information
prev = [0] * (cols + 1)
for i in range(rows):
    for j in range(cols):
        if matrix[i][j] == '1':
            prev[j+1] = min(prev[j], prev[j+1], ???) + 1  # Lost diagonal value!

Correct Space-Optimized Version:

# Need to preserve the diagonal value
prev = [0] * (cols + 1)
for i in range(rows):
    curr = [0] * (cols + 1)
    for j in range(cols):
        if matrix[i][j] == '1':
            curr[j+1] = min(prev[j], prev[j+1], curr[j]) + 1
            max_side = max(max_side, curr[j+1])
    prev = curr