Maximal Sqaure

XXX. Maximal Square

Dynamic Programming

Matrix

Problem Statement:

Given a 2D binary matrix filled with 0's and 1's, find the largest square submatrix that contains all 1's.

• Return area of largest square
• Matrix contains '0' and '1' characters
• Square must be filled with all 1's

Key Points:

• **DP State**:
  • dp[i][j] represents size of largest square ending at (i,j)
  • Use min of three neighbors + 1 for new squares
  • First row/column are base cases
• **Square Formation**:
  • Need all three neighbors to form larger square
  • Size limited by smallest neighbor
  • Track maximum size seen so far

Example:

For matrix:

1 1 1
1 1 1
1 1 1
        

DP array becomes:

1 1 1
1 2 2
1 2 3
        

Maximum square size is 3, area is 9

Implementation:

Java Solution:

public int maximalSquare(char[][] matrix) {
    if (matrix.length == 0) return 0;
    
    int[][] dp = new int[matrix.length][matrix[0].length];
    int max = 0;
    
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            // Handle first row/column
            if ((i == 0 || j == 0) && matrix[i][j] == '1') {
                dp[i][j] = 1;
            } 
            // Check if we can form larger square
            else if (matrix[i][j] == '1') {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], 
                             dp[i-1][j-1]) + 1;
            }
            max = Math.max(dp[i][j], max);
        }
    }
    
    return max * max;  // Return area
}

private int min(int a, int b, int c) {
    return Math.min(Math.min(a, b), c);
}

Python 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_size = 0
    
    for i in range(rows):
        for j in range(cols):
            # Handle first row/column
            if (i == 0 or j == 0) and matrix[i][j] == '1':
                dp[i][j] = 1
            # Check if we can form larger square
            elif matrix[i][j] == '1':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1],
                             dp[i-1][j-1]) + 1
            max_size = max(dp[i][j], max_size)
            
    return max_size * max_size

C++ Solution:

int maximalSquare(vector>& matrix) {
    if (matrix.empty()) return 0;
    
    int rows = matrix.size(), cols = matrix[0].size();
    vector> dp(rows, vector(cols, 0));
    int max_size = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // Handle first row/column
            if ((i == 0 || j == 0) && matrix[i][j] == '1') {
                dp[i][j] = 1;
            }
            // Check if we can form larger square
            else if (matrix[i][j] == '1') {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1],
                              dp[i-1][j-1]}) + 1;
            }
            max_size = max(dp[i][j], max_size);
        }
    }
    
    return max_size * max_size;
}

Complexity:

Time Complexity: O(m×n), where m and n are matrix dimensions
Space Complexity: O(m×n) for DP array