Count zeros in a row wise and column wise sorted matrix

Count zeros in sorted matrix

---

Count zeros in a row wise and column wise sorted matrix Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

There are many approach to solve this problem, Lets see few of them.

Approach 1: 
Initialise counter = 0 and check for each element of the array and increment counter if you encounter 0. This approach is not efficient as in worst case we need to traverse complete matrix to identify whether element is present or not.

Approach 2:
As matrix is sorted, we can apply binary search and identify start position of 0 in each row and sum count of 0 of each row.

Approach 3:
In this approach, we will start our search by looking at Right most element of first row.

1. If Current Element =  1, it means, no need to look down as all element down will be greater than 1 since columns are also sorted. move to next column (decrement column--). 
2. If Current Element = 0, It means all element on left will surely be 0 and without traversing on left side directly add them all together by looking at column index and move to next row (increment row++). 
3. Stop our search if control reaches the bottom left element or all columns are covered. 

Lets take an example and understand the solution:

Java Program to count 0 in sorted matrix

---

package javabypatel;

public class CountZeroInSortedMatrix {

 public static void main(String[] args) {
  new CountZeroInSortedMatrix();
 }

 public CountZeroInSortedMatrix() {
  int[][] arr = {
    {0, 0, 0, 0, 1},
    {0, 0, 0, 1, 1},
    {0, 1, 1, 1, 1},
    {1, 1, 1, 1, 1},
    {1, 1, 1, 1, 1}
  };

  int column=arr[0].length-1;
  int row=0;
  int zeroCount = 0;

  while(row<arr.length && column>=0){ 
   if(arr[row][column] == 1){
    column--;
   }else{
    zeroCount += column+1;
    row++; 
   }
  }
  System.out.println(zeroCount);
 }
}

You may also like to see

---

Search in a row wise and column wise sorted matrix

Find Largest and Smallest number in Array

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.