Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. This problem is known as maximal square area problem. For example,
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
Thought process
What is the basic condition for a square? Basic condition for a square is that its length and breadth should be equal. For any cell to be included into the square, it has to be stretch from three sides: length wise, breadth wise and diagonally. So, to know if a cell will increase the size of the square?
We can recursively find the longest side of the square at each cell i,j. Keep track of the global maximum while getting the side at each cell.
Show me the implementation
class Solution {
int max = 0;
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if(rows == 0) return 0;
int cols = matrix[0].length;
for (int i = rows-1; i >=0; i--)
for (int j = cols-1; j>=0; j--)
max = Math.max(max, maxSquareUtil(matrix, i, j));
return max * max;
}
private int maxSquareUtil(char[][] matrix,
int i, int j){
if(i == 0 || j == 0){
return matrix[i][j] -'0';
}
int c = (matrix[i][j] == '1' ) ? Math.min(
maxSquareUtil(matrix, i-1, j),
Math.min(maxSquareUtil(matrix, i, j-1),
maxSquareUtil(matrix, i-1, j-1))
) + 1 : 0;
return c;
}
}
Now, the two conditions necessary for applying dynamic programming are present: optimal subproblem solution leads to the optimal solution to a bigger problem and there are overlapping subproblems.
What can we do to avoid recalculating the solution from subproblems again and again? We can save solutions to problems in the cache. Whenever we want to solve the problem, we first check in the cache, if it is present, we do not solve it again and use the cache value. If not present, then we calculate it.
Top-down approach
class Solution {
int max = 0;
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if(rows == 0) return 0;
int cols = matrix[0].length;
int [][] cache = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cache[i][j] = -1;
}
for (int i = rows-1; i >=0; i--)
for (int j = cols-1; j>=0; j--)
max = Math.max(max,
maxSquareTopDown(matrix, cache,i, j));
return max * max;
}
private int maxSquareTopDown(char[][] matrix, int[][] cache,
int i, int j){
if(i == 0 || j == 0 || matrix[i][j] == '0' ){
cache[i][j] = matrix[i][j] -'0';
return matrix[i][j] -'0';
}
if(cache[i][j] != -1){
return cache[i][j];
}
cache[i][j] = Math.min(
maxSquareTopDown(matrix, cache, i, j-1),
Math.min(maxSquareTopDown(matrix, cache, i-1, j-1),
maxSquareTopDown(matrix, cache, i-1, j))
) + 1;
return cache[i][j];
}
}
The time complexity of the code is O(n * m) with additional space complexity of O(n * m).
Bottom-up approach
We can think of the problem from the bottom-up view. What will be the size of a square for each cell? If the cell is 1, the size will be 1 and if the cell is 0, then it will be zero.- Construct an array dp[][] for the given matrix[][].
- Copy first row and first columns as it is from matrix[][] to dp[][]
- For other entries, use following expressions to construct dp[][]
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == 1 else 0Find the maximum entry in dp[][] and return its square.
show me the bottom-up implementation
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if(rows == 0) return 0;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols];
for(int i = 0; i < rows; i++){
if(matrix[i][0] == '1') {
max = 1;
dp[i][0] = 1;
}
}
for(int i = 0; i < cols; i++){
if(matrix[0][i] == '1') {
max = 1;
dp[0][i] = 1;
}
}
for(int i = 1; i < rows; i++){
for(int j = 1; j < cols; j++){
if(matrix[i][j] == '1'){
dp[i][j] = Math.min(dp[i-1][j],
Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
max = Math.max(dp[i][j], max);
}
}
}
return max * max;
}