Dare2Solve
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.
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.
Define the Recursive Function with Memoization:
bfs(i, j)
that computes the maximum side length of the square that can be formed ending at cell (i, j)
.Base Cases:
i >= rows
or j >= cols
), return 0 because we cannot form a square beyond the matrix boundaries.Recursive Cases:
bfs
for the downward, diagonal, and rightward positions.Start the Recursion:
bfs(0, 0)
.Return the Result:
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.
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.
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int result = 0;
unordered_map<string, int> cacheMap;
function<int(int, int)> 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);
}
};
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
class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
Map<String, Integer> 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<String, Integer> 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);
}
}
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)
};