Maximal square area

Tags:

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? maximum square area 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;
        
    }
}
It is quite obvious from the solution that the optimal solution of a subproblem leads to the optimal solution of the original problem. However, let’s look at the execution tree of the code. maximal square area 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 0
Find 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;
    }
The time complexity of the code is O(n * m) with additional space complexity of O(n * m).