Q55 Count Square Submatrices with All Ones - LeetCode 1277

PHOTO EMBED

Sat Sep 09 2023 16:44:57 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07 

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length , n = matrix[0].length;
        int dp[][]= new int[m][n];

        int count = 0;
        //meaning of an element in dp -> count of submatrices in for that element
        //traverse reversely
        for(int i = m-1 ; i>=0 ; i--){
            for(int j = n-1; j>=0 ; j--){
                
                //if last row or coloumn , there can be 1 square or none at all
                if(i == m-1 || j == n-1)
                dp[i][j] = matrix[i][j];

                else{
                    if(matrix[i][j] == 0)
                    dp[i][j] = 0;

                    //no. of submatrice = minof(right ,bottom , diagnol) +1;
                    else
                    dp[i][j] = 1+Math.min(dp[i+1][j+1] , Math.min(dp[i+1][j] , dp[i][j+1]));
                }
                
                count+= dp[i][j];
            }
        }
        return count;
    }
}
content_copyCOPY

https://leetcode.com/problems/count-square-submatrices-with-all-ones/