LeetCode 221: Maximal Square Solution in Python Explained

Problem Statement

In LeetCode 221: Maximal Square, you’re given:

• matrix: A 2D array of characters '0' and '1'.
• Your task is to return the area of the largest square submatrix containing only '1's.

The area is the side length squared (e.g., a 2×2 square has area 4). This differs from near-duplicate detection in LeetCode 220: Contains Duplicate III, focusing instead on geometric patterns in a grid.

Constraints

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

Examples

Let’s see some cases:

Copy codeInput: matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 4
Explanation: A 2×2 square of 1s at bottom-right (rows 1-2, cols 3-4).

Copy codeInput: matrix = [["0","1"],["1","0"]]
Output: 1
Explanation: Single 1s, area = 1×1 = 1.

Copy codeInput: matrix = [["0"]]
Output: 0
Explanation: No 1s, area = 0.

These examples show we’re seeking the largest square of 1s.

Understanding the Problem

How do we solve LeetCode 221: Maximal Square in Python? For the first example, the largest square is 2×2 (area 4) in the bottom-right corner. A naive approach might check every possible square (O(m²n²)), but dynamic programming optimizes this. This isn’t a skyline problem like LeetCode 218: The Skyline Problem; it’s about finding the maximal square submatrix. We’ll use: 1. Dynamic Programming: O(mn) time, O(mn) space—our best solution. 2. Brute Force: O(m²n²) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming Approach

Explanation

The Dynamic Programming (DP) approach builds a table:

• dp[i][j]: The side length of the largest square ending at (i,j) with all 1s.
• If matrix[i][j] = '0', dp[i][j] = 0.
• If matrix[i][j] = '1', dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (smallest square above, left, and diagonally plus 1).
• Track the maximum side length and return its square.

This runs in O(mn) time (single pass over the matrix) and O(mn) space (DP table), making it efficient—our best solution.

For the first example, it computes the largest square size systematically.

Step-by-Step Example

Example 1: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Goal: Return 4.

• Step 1: Initialize DP table (m+1 × n+1 for simplicity).
• dp = [[0]*6 for _ in range(5)].
• Step 2: Fill DP table.
• i=0, j=0: matrix[0][0]='1', dp[1][1] = 1.
• i=0, j=1: matrix[0][1]='0', dp[1][2] = 0.
• i=1, j=0: matrix[1][0]='1', dp[2][1] = 1.
• i=1, j=3: matrix[1][3]='1', dp[2][4] = min(0,1,0)+1 = 1.
• i=2, j=2: matrix[2][2]='1', dp[3][3] = min(1,1,0)+1 = 1.
• i=2, j=3: matrix[2][3]='1', dp[3][4] = min(1,1,1)+1 = 2.
• i=2, j=4: matrix[2][4]='1', dp[3][5] = min(1,0,0)+1 = 1.
• Step 3: Compute max side.
• dp table (relevant part):

Copy code```
[1,0,1,0,0]
[1,0,1,1,1]
[1,1,1,2,1]
[1,0,0,1,0]
```

• Max side = 2, area = 4.

Example 2: matrix = [["0","1"],["1","0"]]

Goal: Return 1.

• Step 1: dp = [[0]*3 for _ in range(3)].
• Step 2:
• i=0, j=1: dp[1][2] = 1.
• i=1, j=0: dp[2][1] = 1.
• Step 3: Max side = 1, area = 1.
• Output: 1.

How the Code Works (Dynamic Programming) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef maximalSquare(matrix: list[list[str]]) -> int:
    # Line 1: Get dimensions
    m, n = len(matrix), len(matrix[0])
    # Rows and cols (e.g., 4, 5)

    # Line 2: Initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # Extra row/col for base cases (e.g., 5×6 zeros)
    max_side = 0
    # Track largest square side (e.g., 0)

    # Line 3: Fill DP table
    for i in range(m):
        # Iterate rows (e.g., 0 to 3)
        for j in range(n):
            # Iterate cols (e.g., 0 to 4)
            if matrix[i][j] == '1':
                # Current cell is 1 (e.g., matrix[2][3])
                dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1
                # Min of neighbors + 1 (e.g., min(1,1,1)+1=2)
                max_side = max(max_side, dp[i + 1][j + 1])
                # Update max (e.g., max(1,2)=2)

    # Line 4: Return area
    return max_side * max_side
    # Area of largest square (e.g., 2*2=4)

This solution efficiently computes the largest square using DP.

Alternative: Brute Force Approach

Explanation

The Brute Force approach checks all possible squares:

• For each '1', expand outward to find the largest square with that bottom-right corner.
• Check all cells in the square are '1'.
• Track the maximum side length.

It’s O(m²n²) time (checking all squares) and O(1) space, simple but slow.

Step-by-Step Example

For [["1","0"],["1","1"]]:

• (0,0): 1×1, area=1.
• (1,0): 1×1, area=1.
• (1,1): Try 1×1 (1), 2×2 (top-left 0 fails), max=1.
• Output: 1.

How the Code Works (Brute Force)

Copy codedef maximalSquareBrute(matrix: list[list[str]]) -> int:
    m, n = len(matrix), len(matrix[0])
    max_side = 0

    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                side = 1
                while i + side < m and j + side < n:
                    if all(matrix[i + r][j + c] == '1' for r in range(side + 1) for c in range(side + 1)):
                        side += 1
                    else:
                        break
                max_side = max(max_side, side)

    return max_side * max_side

Complexity

• Dynamic Programming:
• Time: O(mn) – single pass over matrix.
• Space: O(mn) – DP table.
• Brute Force:
• Time: O(m²n²) – check all squares.
• Space: O(1) – no extra space.

Efficiency Notes

Dynamic Programming is our best solution with O(mn) time, ideal for this problem. Brute Force is intuitive but impractical for large matrices.

Key Insights

• DP: Builds on smaller squares.
• Square: All 1s in submatrix.
• Area: Side length squared.

Additional Example

For [["1","1"],["1","1"]]:

• DP: dp=[[1,1],[1,2]], area=4.
• Brute: Finds 2×2, area=4.

Edge Cases

• All 0s: 0.
• Single 1: 1.
• Single cell: 0 or 1.

Both handle these well.

Final Thoughts

LeetCode 221: Maximal Square in Python is a classic DP challenge. Dynamic Programming offers speed and elegance, while Brute Force provides a baseline. Want more? Try LeetCode 85: Maximal Rectangle or LeetCode 1277: Count Square Submatrices with All Ones. Test your skills—Solve LeetCode 221 on LeetCode with the first example (expecting 4)—find that maximal square today!