Count number of zeros in a Row-wise Col-wise sorted binary matrix

Given a binary matrix with all rows and col sorted. Write code to count the number of zeros in that matrix.

For example, if the matrix is

[0, 0, 0, 0, 1]
[0, 0, 0, 1, 1]
[0, 1, 1, 1, 1]
[0, 1, 1, 1, 1]
[1, 1, 1, 1, 1]

Then output should be 9, because there are 9 zeros in the matrix.

Solution:

The brute-force solution is obviously O(n2) time solution that traverse the entire matrix and increment the count when element is zero.

int countZeros(int arr[N][N])
{
    int cnt = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(arr[i][j] == 0)
                cnt++
    return cnt;
}

A better solution is to use the logic similar to this post where we are searching in a row-wise column-wise sorted matrix. We start from the top-right cell and follow the below logic:

if(current element is 1)
    Ignore the current column, and continue.
else
    All values before current cell are zeros. Add (row+1) to total count, increment the row and move forward.

The code for this logic is as below (for a change, let us write the code in Java):

class DemoClass
{
    public static int countZeros(int arr[][])
    {
        int cnt = 0;
        // STARTING POINT
        int row = 0;
        int col = arr[0].length-1;
        while(row=0)
        {
            if(arr[row][col] == 1)
            {
                col--;
            }
            else
            {
                cnt += col+1;
                row++;
            }
        }
        return cnt;
    }
    public static void main(String[] args)
    {
        int arr[][] = { {0, 0, 0, 0, 1},
                        {0, 0, 0, 1, 1},
                        {0, 0, 1, 1, 1},
                        {0, 1, 1, 1, 1},
                        {1, 1, 1, 1, 1}};
        System.out.println("NUMBER OF ZEROS :"+countZeros(arr));
    }
}

The time taken by above logic is linear, i.e O(n).

Read more about searching and sorting techniques in our book: "Searching and Sorting for Coding Interviews"