Count Square Submatrices with all Ones

Moderate
0/80
profile
Contributed by
23 upvotes
Asked in companies
AmazonGoogle inc

Problem statement

A matrix 'arr' with 'n' rows and 'm' columns is given.


Count the number of square submatrices in matrix ‘arr’ with all elements equal to 1.


A square matrix is a matrix with square dimensions.


Example : 
Input: If 'n' = 2, 'm' = 2, and 'arr' = [ [1, 1], [1, 1] ].

Output: 5

Explanation: We have 4 square submatrices of size 1*1 and 1 square submatrix of size 2*2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains two space-separated integers, ‘n’ and ‘m,’ denoting the number of rows and columns, respectively.

The following 'n' lines contain 'm' integers each, denoting the values of the matrix.
Output Format : 
Print an integer representing the number of square submatrices.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Sample Input 1 :
2 2
1 0
0 1
Sample Output 1 :
2
Explanation of sample input 1:
There are two square submatrices of size 1*1, so the answer is 2.
Sample Input 2 :
3 4
0 1 1 0
1 1 1 0
0 0 1 0
Sample Output 2 :
7
Explanation of sample input 2:
There are six square submatrices of size 1*1, and there is one square submatrix of size 2*2. So, the answer is 6 + 1 = 7.
Expected time complexity:
The expected time complexity is O(n*m), where 'n' and 'm' are the dimensions of the matrix.
Constraints :
1 ≤ 'n', 'm' ≤ 1000
0 ≤ 'arr'[i][j] ≤ 1

Time limit: 1 sec
Hint

Fix one corner of the square submatrix and apply Prefix sums.

Approaches (2)
Brute Force Approach

A brute-force approach is to iterate over all the square submatrices and check if they contain all ones.

 

This approach is too slow. The 2nd part of determining if this square submatrix contains all ones can be optimized.  We can store prefix sums for each cell. Then we can check if this submatrix has all ones in constant time. 

 

How to calculate prefix sums for a matrix?

Suppose we are in a cell (r, c). Then we can add prefix sums of (r - 1, c) and (r, c - 1) along with arr[r][c], but we have counted (r - 1, c - 1) two times. So we will subtract that once.

So, the relation becomes pref[r][c] = arr[r][c] + pref[r - 1][c] + pref[r][c - 1] - pref[r - 1][c - 1] (where pref[i][j] denotes the sum of the submatrix which has the top left corner at (0, 0) and the bottom right corner at (i, j)

Note that, for the first row, or first column, some of the terms do not exist. So, we can take them 0.

 

The steps are as follows:

  1. Calculate the prefix sum matrix for the given matrix. Also, declare and initialize a variable ‘ans’ to ‘0’.
  2. Iterate over all the upper-left corners of the square. Then iterate over the size of the square to check if it contains all ones.
  3. Suppose the current upper-left corner has coordinates i, j, and the size of the square is s * s. Then the bottom-right corner has coordinates will be i + s - 1, j + s - 1.
  4. Find the sum of this square using prefix sums and check if this sum equals s * s. If it is, then increment the answer count.
  5. Return the answer.
Time Complexity

O( N * M * min ( N, M ) ) where N and M denote the number of rows and columns, respectively.

 

We can calculate prefix sums in O( N * M ) time.  For each cell, we take ~O( 1 ) operations for each cell to calculate the prefix sums, and there are N * M cells in total.

We then iterate over all the upper-left corners of the submatrix, there are N * M possibilities here. For each upper-left corner, there are ~O( min( N, M ) ) square submatrices to be explored.

The sum of each square matrix can be computed in constant time using the prefix sum matrix. 

 

Hence, the time complexity is O( N * M * min ( N, M ) ).

Space Complexity

O( 1 )
 

No extra space is needed. We may use the original matrix itself to store the prefix sum.

 

Hence, the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Count Square Submatrices with all Ones
Full screen
Console