Count zeros in a row wise and column wise sorted matrix

Last Updated : 19 Aug, 2022

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>

Output

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.

Suggest improvement

Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X'

Queries in a Matrix

Share your thoughts in the comments

Basic Operations on Matrix

Easy problems on Matrix

Intermediate problems on Matrix

Hard problems on Matrix