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,
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.
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.
- 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--).
- 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++).
- 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.
Post a Comment