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

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

Given: a binary matrix with sorted rows and columns.

Example: If the matrix is :

[0, 0, 0, 1]

[0, 0, 1, 1]

[0, 1, 1, 1]

[1, 1, 1, 1]

Then output should be 6, because there are 6 zeros in the matrix.

# Approach

The entire matrix is traversed and the count of zeros is incremented.

Code:

#include <iostream>

// C++ program to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.

// define size of square matrix
const int N = 5;

// Function to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.
int zerocount(int mat[N][N])
{
    // starting from bottom -left corner of matrix
    int rows = N - 1, column = 0;

    // variable storing number of zeroes
    int count = 0;

    while (column < N)
    {
        // going up till we find a 0
        while (mat[rows][column])
        // if zero is not found in present column,
        //we are done
        if (--rows < 0)
            return count;

        // add number of 0s present in current column to the answer
        count += (rows + 1);

        // moving right to next the column
        column++;
    }

    return count;
}

// main function
int main()
{
    int mat[N][N] =
        {
            { 0, 0, 0, 0, 0 },
            { 0, 0, 0, 1, 1 },
            { 0, 0, 0, 1, 1 },
            { 0, 0, 1, 1, 1 },
            { 1, 1, 1, 1, 1 }
        };

    std::cout << zerocount(mat);

    return 0;
}

Output

TIME COMPLEXITY: The time complexity of this code is O(n2)