Sum Of Zeroes

Easy
0/40
Average time to solve is 10m
profile
Contributed by
65 upvotes
Asked in companies
SprinklrCompass Group

Problem statement

You are given a binary matrix (it contains only 0s and 1s) with dimensions ‘N * M’. You need to find and return the sum of coverages of all zeros of the given matrix.

Coverage for a particular 0 is defined as the total number of ‘1s’ around it (i.e., immediate left, immediate right, immediate up, and immediate bottom positions).

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of the test cases. Then ‘T' test cases follow.

The first line of each test case contains two space-separated integers, 'N', 'M', the dimensions of the matrix. 

Next ‘N’ lines consist of ‘M’ space-separated integers denoting the matrix elements. Each element is either 0 or 1, as described in the problem statement.
Output Format: 
For each test case, return the sum of coverage of all the 0s in the matrix.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10^3

Time limit: 1 second
Sample Input 1:
1
2 2 
1 0
0 1
Sample Output 1:
4
Explanation of Input 1:
In the given matrix, there are 2 zeros. 
For the 0 at the 1st row, 2nd column position, coverage is 2(there is 1 adjacent top one and 1 adjacent right one).
For the 0 at the 2nd row, 2nd column the coverage is 2(there is 1 adjacent top one and 1 adjacent right one).

Hence the net coverage is 2 + 2 = 4.
Sample Input 2:
1
2 3
0 0 0
0 0 0
Sample Output 2
0
Hint

Try to find a brute force approach.


 

Approaches (1)
Brute Force Approach:

For any 0 we just need to check its four adjacent sides and look for 1s in them. Therefore we could simply traverse the matrix, and if the current element is a 0, check how many of its adjacent neighbors are 1s and add this value to an integer variable ANS representing the result. In the end, return the value of ANS.

 

Steps:

  • Keep a variable ANS which will store our answer.
  • Traverse the matrix. Suppose i denotes the current row and j denotes the current column (1 <= i <= N, 1 <= j <= M).
    • Let’s say the given matrix is MAT.
    • If the current element is 0 then
      • If Mat[i-1][j](top neighbour) is 1, increment value of ANS by 1.
      • If Mat[i+1][j](bottom neighbour) is 1, increment value of ANS by 1.
      • If Mat[i][j-1](left neighbour) is 1, increment value of ANS by 1.
      • If Mat[i][j+1](right neighbour) is 1, increment value of ANS by 1.
Time Complexity

O(N*M), where N and M are the rows and columns of the input matrix respectively.
 

As we traverse the matrix of size ‘N*M’ for a single time. Therefore the net time complexity is O(N*M).

Space Complexity

O(1)
 

As we are using constant space.

Code Solution
(100% EXP penalty)
Sum Of Zeroes
Full screen
Console