
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
- 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. - Base Cases:
- If the indices exceed the matrix boundaries (i.e.,
i >= rows
orj >= cols
), return 0 because we cannot form a square beyond the matrix boundaries. - 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. - Start the Recursion:
- Start the recursion from the top-left corner of the matrix by calling
bfs(0, 0)
. - 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)
};