# Interview Questions

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

- December 29, 2017
- Posted by: Kamal Rawat
- Category: Algorithms

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“