1277. Count Square Submatrices with All Ones

1277. 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:

Brute Force: We can go to each position and get the maximum size of the square if it is the starting square using some for loops and conditions. But this will be complex. Let's move to dynamic programming.

Dynamic Programming:

We can make a matrix of the same size as the input. The first row and the first column of this will be the same size as the input as the size of the square will be 1 if it is  1 or else it will be zero,

Input:

1	1	1
1	1	1
1	1	1

Matrix made by us:

1	1	1
1	2	2
1	2	3

 DP state:

if(arr[i][j]==1) dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});

Why we are taking the minimum of all three is because we need to make a square so the top, left and the previous diagonal should be 1 then only the size of the square will increase.

Now we can find the answer as the sum of all the numbers in the DP and the largest number will be the side of the largest square possible.

 

Time Complexity: O(N²)

Space Complexity: O(N²)