221. Maximal Square

Jump to Solution: Python Java C++ JavaScript C#

Problem 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.

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Python Solution

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
            
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        max_side = 0
        
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if matrix[i-1][j-1] == '1':
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    max_side = max(max_side, dp[i][j])
        
        return max_side * max_side

Time Complexity: O(m*n)

Where m and n are the dimensions of the matrix.

Space Complexity: O(m*n)

For the DP array.

Java Solution

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        
        return maxSide * maxSide;
    }
}

Time Complexity: O(m*n)

Where m and n are the dimensions of the matrix.

Space Complexity: O(m*n)

For the DP array.

C++ Solution

class Solution {
public:
    int maximalSquare(vector>& matrix) {
        if (matrix.empty()) {
            return 0;
        }
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector> dp(rows + 1, vector(cols + 1, 0));
        int maxSide = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        
        return maxSide * maxSide;
    }
};

Time Complexity: O(m*n)

Where m and n are the dimensions of the matrix.

Space Complexity: O(m*n)

For the DP array.

JavaScript Solution

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0) {
        return 0;
    }
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    const dp = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
    let maxSide = 0;
    
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (matrix[i-1][j-1] === '1') {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    
    return maxSide * maxSide;
};

Time Complexity: O(m*n)

Where m and n are the dimensions of the matrix.

Space Complexity: O(m*n)

For the DP array.

C# Solution

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if (matrix == null || matrix.Length == 0) {
            return 0;
        }
        
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[,] dp = new int[rows + 1, cols + 1];
        int maxSide = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i,j] = Math.Min(Math.Min(dp[i-1,j], dp[i,j-1]), dp[i-1,j-1]) + 1;
                    maxSide = Math.Max(maxSide, dp[i,j]);
                }
            }
        }
        
        return maxSide * maxSide;
    }
}

Time Complexity: O(m*n)

Where m and n are the dimensions of the matrix.

Space Complexity: O(m*n)

For the DP array.

Approach Explanation

The solution uses dynamic programming to efficiently find the largest square submatrix containing only 1's. Here's how it works:

Create a DP array:
- dp[i][j] represents the side length of the maximum square ending at position (i,j)
- Add an extra row and column of zeros for easier handling of edge cases
For each cell (i,j) in the matrix:
- If the cell contains '1', look at three adjacent cells in the dp array
- Take the minimum of these three values and add 1
- This gives us the largest possible square ending at this cell
Keep track of the maximum side length seen so far
Return the area (square of the maximum side length)

The key insight is that for a square to exist, it must be supported by valid squares at its top, left, and top-left positions. The minimum of these three positions plus 1 gives us the largest possible square ending at the current position.