14.16 Maximal Square

14.16.1 Problem Metadata

14.16.2 Description

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.

14.16.3 Examples

Example 1:

Input: matrix = [["1","0","1","0","0"],
                 ["1","0","1","1","1"],
                 ["1","1","1","1","1"],
                 ["1","0","0","1","0"]]
Output: 4
Explanation: The largest square has side length 2, so area = 2 * 2 = 4

Example 2:

Input: matrix = [["0","1"],
                 ["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

14.16.4 Constraints

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

14.16.5 Solution - Dynamic Programming

14.16.5.1 Walkthrough

The key insight is that for any cell (r, c) containing '1', the maximum square with that cell as the bottom-right corner depends on the minimum of three neighboring squares:

  1. The square ending at (r-1, c) (cell above)
  2. The square ending at (r, c-1) (cell to the left)
  3. The square ending at (r-1, c-1) (diagonal cell)

If all three neighbors can form squares of side length k, then the current cell can form a square of side length k+1. This is because: - The top neighbor ensures we have k rows of 1’s above - The left neighbor ensures we have k columns of 1’s to the left - The diagonal neighbor ensures the k x k square is filled with 1’s

We use a DP table where dp[r][c] represents the side length of the largest square whose bottom-right corner is at (r, c).

Example Walkthrough:

For the matrix:

["1","0","1","0","0"]
["1","0","1","1","1"]
["1","1","1","1","1"]
["1","0","0","1","0"]

The DP table builds as:

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

The maximum side length is 2, so the area is 2 × 2 = 4.

14.16.5.2 Analysis

  • Time Complexity: O(m × n) - Single pass through the matrix
  • Space Complexity: O(m × n) - DP table storage (can be optimized to O(n) using rolling arrays)

14.16.5.3 Implementation Steps

  1. Initialize a DP table dp[rows][cols] and max_side = 0
  2. For each cell (r, c):
    • If matrix[r][c] == '1':
      • If it’s in the first row or first column, dp[r][c] = 1 (can only form 1×1 square)
      • Otherwise, dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
      • Update max_side with the maximum side length seen
    • If matrix[r][c] == '0', set dp[r][c] = 0
  3. Return max_side × max_side (area = side²)

14.16.5.4 Code - Java

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int max_side = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // Only process cells containing '1'
                if (matrix[r][c] == '1') {
                    // Base case: first row or first column
                    // Can only form a 1x1 square
                    if (r == 0 || c == 0) {
                        dp[r][c] = 1;
                    } else {
                        // DP transition: current square size is limited by
                        // the minimum of the three neighbors + 1
                        int min = Math.min(dp[r - 1][c], dp[r][c - 1]);
                        min = Math.min(min, dp[r - 1][c - 1]);
                        dp[r][c] = min + 1;
                    }

                    // Track the maximum side length encountered
                    max_side = Math.max(max_side, dp[r][c]);
                } else {
                    // Cell contains '0', cannot form a square
                    dp[r][c] = 0;
                }
            }
        }

        // Return area (side length squared)
        return max_side * max_side;
    }
}