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 0Output: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; } }

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**

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

`O(n * m)`with additional space complexity of

`O(n * m)`.