221. Maximal Square

Description

The problem is to find the largest square containing only 1s in a 2D binary matrix and return its area. The matrix consists of '0's and '1's, and we need to determine the area of the largest square submatrix that contains only '1's.

Intuition

To solve this problem, we can use dynamic programming (DP). The idea is to use a DP table to keep track of the maximum side length of the square that can be formed ending at each cell in the matrix. By breaking the problem into smaller subproblems, we can efficiently compute the solution using memoization to avoid redundant calculations.

Approach

1. Define the Recursive Function with Memoization: - Create a recursive function bfs(i, j) that computes the maximum side length of the square that can be formed ending at cell (i, j). - Use a cache (dictionary) to store the results of subproblems to avoid redundant calculations.
2. Base Cases: - If the indices exceed the matrix boundaries (i.e., i >= rows or j >= cols), return 0 because we cannot form a square beyond the matrix boundaries.
3. Recursive Cases: - If the value at the current cell is already computed and stored in the cache, return the cached value. - Calculate the maximum side length of the square by recursively calling bfs for the downward, diagonal, and rightward positions. - If the current cell contains '1', the side length of the square ending at this cell is 1 plus the minimum of the side lengths obtained from the downward, diagonal, and rightward positions. - Store the computed value in the cache and return it.
4. Start the Recursion: - Start the recursion from the top-left corner of the matrix by calling bfs(0, 0).
5. Return the Result: - Determine the maximum side length from the cache values and return its square as the area of the largest square.

Complexity

Time Complexity:

O(m * n), where m is the number of rows and n is the number of columns in the matrix. Each cell is processed once, and the result is stored in the cache to avoid redundant calculations.

Space Complexity:

O(m * n), for the cache that stores the results of subproblems. In the worst case, the cache will store the results for all cells in the matrix.

Code

C++

class Solution {
public:
    int maximalSquare(vector>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int result = 0;
        unordered_map cacheMap;
        function bfs = [&](int i, int j) {
            if (i >= rows || j >= cols) {
                return 0;
            }
            string key = to_string(i) + "," + to_string(j);
            if (cacheMap.find(key) == cacheMap.end()) {
                int down = bfs(i + 1, j);
                int diag = bfs(i + 1, j + 1);
                int right = bfs(i, j + 1);
                cacheMap[key] = 0;
                if (matrix[i][j] == '1') {
                    cacheMap[key] = 1 + min({down, diag, right});
                }
            }
            return cacheMap[key];
        };
        bfs(0, 0);
        int maxLen = 0;
        for (const auto& entry : cacheMap) {
            maxLen = max(maxLen, entry.second);
        }
        return pow(maxLen, 2);
    }
};

Python

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        cache = {}
        def bfs(i, j):
            if i >= rows or j >= cols:
                return 0
            if (i, j) not in cache:
                down = bfs(i + 1, j)
                diag = bfs(i + 1, j + 1)
                right = bfs(i, j + 1)
                cache[(i, j)] = 0
                if matrix[i][j] == '1':
                    cache[(i, j)] = 1 + min(down, diag, right)
            return cache[(i, j)]
        bfs(0, 0)
        max_len = max(cache.values(), default=0)
        return max_len ** 2

Java

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        Map cacheMap = new HashMap<>();
        
        int maxLen = bfs(0, 0, matrix, rows, cols, cacheMap);
        int result = 0;
        for (int value : cacheMap.values()) {
            result = Math.max(result, value);
        }
        return result * result;
    }
    private int bfs(int i, int j, char[][] matrix, int rows, int cols, Map cacheMap) {
        if (i >= rows || j >= cols) {
            return 0;
        }
        String key = i + "," + j;
        if (!cacheMap.containsKey(key)) {
            int down = bfs(i + 1, j, matrix, rows, cols, cacheMap);
            int diag = bfs(i + 1, j + 1, matrix, rows, cols, cacheMap);
            int right = bfs(i, j + 1, matrix, rows, cols, cacheMap);
            cacheMap.put(key, 0);
            if (matrix[i][j] == '1') {
                cacheMap.put(key, 1 + Math.min(down, Math.min(diag, right)));
            }
        }
        return cacheMap.get(key);
    }
}

JavaScript

var maximalSquare = function(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let result = 0
    const cacheMap = new Map();
    const bfs = (i,j) => {
        if ((i >= rows) || (j >= cols)) {
            return 0
        }
        if (!cacheMap.has(`${i},${j}`)) {
            let down = bfs(i+1, j)
            let diag = bfs(i+1, j+1)
            let right = bfs(i, j+1)
            cacheMap.set(`${i},${j}`, 0)
            if (matrix[i][j] === '1') {
                cacheMap.set(`${i},${j}`, 1 + Math.min(down, diag, right))
            }
        }
        return cacheMap.get(`${i},${j}`)
    }
    bfs(0,0)
    let maxLen = Math.max(...Array.from(cacheMap.values()))
    return Math.pow(maxLen, 2)
};