Count zeros in a row wise and column wise sorted matrix
Given a N x N binary matrix (elements in matrix can be either 1 or 0) where each row and column of the matrix is sorted in ascending order, count number of 0s present in it.
Expected time complexity is O(N).
Examples:
Input: [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] Output: 8 Input: [0, 0] [0, 0] Output: 4 Input: [1, 1, 1, 1] [1, 1, 1, 1] [1, 1, 1, 1] [1, 1, 1, 1] Output: 0
The idea is very simple. We start from the bottom-left corner of the matrix and repeat below steps until we find the top or right edge of the matrix.
- Decrement row index until we find a 0.
- Add number of 0s in current column i.e. current row index + 1 to the result and move right to next column (Increment col index by 1).
The above logic will work since the matrix is row-wise and column-wise sorted. The logic will also work for any matrix containing non-negative integers.
Below is the implementation of above idea :
C++
// C++ program to count number of 0s in the given // row-wise and column-wise sorted binary matrix. #include <iostream> using namespace std; // define size of square matrix #define N 5 // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. int countZeroes( int mat[N][N]) { // start from bottom-left corner of the matrix int row = N - 1, col = 0; // stores number of zeroes in the matrix int count = 0; while (col < N) { // move up until you find a 0 while (mat[row][col]) // if zero is not found in current column, // we are done if (--row < 0) return count; // add 0s present in current column to result count += (row + 1); // move right to next column col++; } return count; } // Driver Program to test above functions int main() { int mat[N][N] = { { 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 } }; cout << countZeroes(mat); return 0; } |
C
// C program to count number of 0s in the given // row-wise and column-wise sorted binary matrix. #include <stdio.h> // define size of square matrix #define N 5 // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. int countZeroes( int mat[N][N]) { // start from bottom-left corner of the matrix int row = N - 1, col = 0; // stores number of zeroes in the matrix int count = 0; while (col < N) { // move up until you find a 0 while (mat[row][col]) // if zero is not found in current column, // we are done if (--row < 0) return count; // add 0s present in current column to result count += (row + 1); // move right to next column col++; } return count; } // Driver Program to test above functions int main() { int mat[N][N] = { { 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 } }; printf ( "%d" ,countZeroes(mat)); return 0; } // This code is contributed by kothavvsaakash. |
Java
// Java program to count number of 0s in the given // row-wise and column-wise sorted binary matrix import java.io.*; class GFG { public static int N = 5 ; // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. static int countZeroes( int mat[][]) { // start from bottom-left corner of the matrix int row = N - 1 , col = 0 ; // stores number of zeroes in the matrix int count = 0 ; while (col < N) { // move up until you find a 0 while (mat[row][col] > 0 ) // if zero is not found in current column, // we are done if (--row < 0 ) return count; // add 0s present in current column to result count += (row + 1 ); // move right to next column col++; } return count; } // Driver program public static void main (String[] args) { int mat[][] = { { 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 } }; System.out.println(countZeroes(mat)); } } // This code is contributed by Pramod Kumar |
Python
# Python program to count number # of 0s in the given row-wise # and column-wise sorted # binary matrix. # Function to count number # of 0s in the given # row-wise and column-wise # sorted binary matrix. def countZeroes(mat): # start from bottom-left # corner of the matrix N = 5 ; row = N - 1 ; col = 0 ; # stores number of # zeroes in the matrix count = 0 ; while (col < N): # move up until # you find a 0 while (mat[row][col]): # if zero is not found # in current column, we # are done if (row < 0 ): return count; row = row - 1 ; # add 0s present in # current column to result count = count + (row + 1 ); # move right to # next column col = col + 1 ; return count; # Driver Code mat = [[ 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 ]]; print ( countZeroes(mat)); # This code is contributed # by chandan_jnu |
C#
// C# program to count number of // 0s in the given row-wise and // column-wise sorted binary matrix using System; class GFG { public static int N = 5; // Function to count number of // 0s in the given row-wise and // column-wise sorted binary matrix. static int countZeroes( int [,] mat) { // start from bottom-left // corner of the matrix int row = N - 1, col = 0; // stores number of zeroes // in the matrix int count = 0; while (col < N) { // move up until you find a 0 while (mat[row,col] > 0) // if zero is not found in // current column, // we are done if (--row < 0) return count; // add 0s present in current // column to result count += (row + 1); // move right to next column col++; } return count; } // Driver Code public static void Main () { int [,] mat = { { 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 } }; Console.WriteLine(countZeroes(mat)); } } // This code is contributed by KRV. |
PHP
<?php // PHP program to count number // of 0s in the given row-wise // and column-wise sorted // binary matrix. // Function to count number // of 0s in the given // row-wise and column-wise // sorted binary matrix. function countZeroes( $mat ) { // start from bottom-left // corner of the matrix $N = 5; $row = $N - 1; $col = 0; // stores number of // zeroes in the matrix $count = 0; while ( $col < $N ) { // move up until // you find a 0 while ( $mat [ $row ][ $col ]) // if zero is not found // in current column, we // are done if (-- $row < 0) return $count ; // add 0s present in // current column to result $count += ( $row + 1); // move right to // next column $col ++; } return $count ; } // Driver Code $mat = array ( array (0, 0, 0, 0, 1), array (0, 0, 0, 1, 1), array (0, 1, 1, 1, 1), array (1, 1, 1, 1, 1), array (1, 1, 1, 1, 1)); echo countZeroes( $mat ); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program to count number of 0s in the given // row-wise and column-wise sorted binary matrix let N = 5; // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. function countZeroes(mat) { // start from bottom-left corner of the matrix let row = N - 1, col = 0; // stores number of zeroes in the matrix let count = 0; while (col < N) { // move up until you find a 0 while (mat[row][col] > 0) // if zero is not found in current column, // we are done if (--row < 0) return count; // add 0s present in current column to result count += (row + 1); // move right to next column col++; } return count; } // Driver code let mat = [[ 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 ]]; document.write(countZeroes(mat)); </script> |
8
Time complexity of above solution is O(n) since the solution follows single path from bottom-left corner to top or right edge of the matrix.
Auxiliary space used by the program is O(1). since no extra space has been taken.
Contact Us