MAY-21 2020 Challenge

Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300

1 <= arr[0].length <= 300

0 <= arr[i][j] <= 1

Solution in C++

class Solution {

public:

    int n,m,cnt=0;

    int mat[302][302],dp[302][302];

    int  dfs(int i,int j)

    {

        if(i>=n||j>=m)

            return 0;

        if(mat[i][j]==0)

            return 0;

        if(dp[i][j]!=-1)

            return dp[i][j];

        int p=dfs(i+1,j);

        int q=dfs(i,j+1);

        int r=dfs(i+1,j+1);

        return dp[i][j]=1+min(p,min(q,r));

    }

    int countSquares(vector<vector<int>>& matrix) {

        int ans=0;

        for(int i=0;i<matrix.size();i++)

        {

            

            for(int j=0;j<matrix[i].size();j++)

            {

               mat[i][j]=matrix[i][j];

            }

        }

        memset(dp,-1,sizeof(dp));

        n=matrix.size();

        m=matrix[0].size();

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<m;j++)

            {

                if(mat[i][j]==1)

                {

                   ans+= dfs(i,j);

                }}}

        return ans;

    }};