Sum Of Zeroes
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).

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

Question

Sum Of Zeroes

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).

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

As we are using constant space.

Time Complexity: O(n^2)Explanation:

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).

Python (3.5)

'''

    Time Complexity O(N*M)

    Space Complexity: O(1)



    where N and M are the dimensions of the input array.

'''



def coverageOfMatrix(mat):



    n = len(mat)

    m = len(mat[0])

    

    # This variable stores our answer.

    ans = 0



    for i in range(n):

        for j in range(m):



            # If current element is 1 then we do need to check for neighbours

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

                continue



            # If left neighbour is 1: increment ans by 1

            if(i-1 >= 0):

                ans += mat[i-1][j]



            # If top neighbour is 1: increment ans by 1

            if(j+1 < m):

                ans += mat[i][j+1]



            # If right neighbour is 1: increment ans by 1

            if(i+1 < n):

                ans += mat[i+1][j]



            # If bottom neighbour is 1: increment ans by 1

            if(j-1 >= 0):

                ans += mat[i][j-1]

            

    # Return the final answer.

    return ans

C++ (g++ 5.4)

/*

    Time Complexity O(N*M)

    Space Complexity: O(1)



    where N and M are the dimensions of the input array.

*/



int coverageOfMatrix(vector> &mat) {

    int n = mat.size();

    int m = mat[0].size();



    // This variable stores our answer.

    int ans = 0;



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

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

            

            // If current element is 1 then we do not need to check for neighbours

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

                continue;

            }

            // If left neighbour is 1: increment ans by 1

            if(i-1 >= 0){

                ans += mat[i-1][j];

            }

            // If top neighbour is 1: increment ans by 1

            if(j+1 < m){

                ans += mat[i][j+1];

            }

            // If right neighbour is 1: increment ans by 1

            if(i+1 < n){

                ans += mat[i+1][j];

            }

            // If bottom neighbour is 1: increment ans by 1

            if(j-1 >= 0){

                ans += mat[i][j-1];

            }

        }

    }



    // Return the final answer.

    return ans;

}

Java (SE 1.8)

/*

    Time Complexity O(N*M)

    Space Complexity: O(1)



    where N and M are the dimensions of the input array.

*/



import java.util.ArrayList;



public class Solution {



    public static Integer coverageOfMatrix(ArrayList> mat) {



        int n = mat.size();

        int m = mat.get(0).size();



        // This vector stores our answer.

        int ans = 0;



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

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



                // If current element is 1 then we do need to check for neighbours

                if(mat.get(i).get(j) == 1){

                    continue;

                }



                // If left neighbour is 1: increment ans by 1

                if (i - 1 >= 0) {

                    ans += mat.get(i - 1).get(j);

                }



                // If top neighbour is 1: increment ans by 1

                if (i + 1 < n) {

                    ans += mat.get(i + 1).get(j);

                }



                // If right neighbour is 1: increment ans by 1

                if (j - 1 >= 0) {

                    ans += mat.get(i).get(j - 1);

                }



                // If bottom neighbour is 1: increment ans by 1

                if (j + 1 < m) {

                    ans += mat.get(i).get(j + 1) ;

                }

            }

        }



        // Return the final answer.

        return ans;

    }

}