May LeetCode Challenge Day 21: Count Square Submatrices with All Ones- (in-place solution)

A trick to solving this problem efficiently is that, we keep track of and update something I would call a square completer. A square completer is the bottom right element of a square that completes the square. For example the dark shaded area below is the square completer of the light shaded areas.

Now the first row and the first columns are excluded from the calculation because they never complete any squares.

So starting from the second row of second column we check if each completes a square. The size of square it completes is the minimum( among its top, top-left and top-left-diagonal elements) + 1. As we move through the array we keep a count of each Square completer’s value and update them as we traverse through the array.

Then, we count the 1 sized squares in the first row and column we excluded earlier. The total count gives the required solution.

Full solution:

class Solution {
    public int countSquares(int[][] matrix) { 
        int count = 0;
 
// Traversing through the array determining square completer values
        
        for(int i = 1; i < matrix.length; i ++){
            for(int j = 1; j < matrix[i].length; j ++){
                int val = checkSquare(matrix,i,j);
                if(val != 0){
                    matrix[i][j] = val+1;
                }
                count += matrix[i][j]; 
            }
        }
// Counting the excluded areas
        for(int i = 0; i < matrix.length; i ++){
            count+=matrix[i][0];
        }
        
        for(int j = 1; j < matrix[0].length; j ++){
            count+=matrix[0][j];
        }  
        
        
        return count;
    }
    
// Check if square
    public int checkSquare(int [][] matrix, int x, int y){
        if (matrix [x][y] == 0 
            || matrix [x][y-1] == 0 
            ||  matrix [x-1][y] == 0  
            || matrix [x-1][y-1] == 0 ){
            return 0;
        }
         
        int min = Math.min(matrix [x][y-1],matrix [x-1][y]);
        return Math.min(matrix [x-1][y-1],min);
        
    }
}