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?
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; } }

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; }