Count Zeros in a row wise and column wise sorted matrix

Introduction

This blog covers a matrix problem. Matrices are one of the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that involves 

counting the number of zeros in a binary matrix where each matrix row and column is sorted in ascending order.

Problem Statement

Ninja is given a N x N binary matrix in which every row and column of the matrix is sorted in non-decreasing order. He is challenged to count zeros present in it. Seems easy right, but the time complexity of the solution should be O(N). Can you help him with this task?

Sample Examples

Example 1

Input

Output

6

Explanation

There are 6 zeroes in the matrix while we traverse it for our operation to count zeros. The matrix is sorted in ascending order. Hence they are present before the 1’s.

Example 2

Input

Output

1

Explanation

There are 6 zeroes in the matrix while we traverse it for our operation to count zeros. The matrix is sorted in ascending order. Hence they are present before the 1’s.

Approach

We would start from the bottom-left corner of the 2-d array and start decreasing the row index until a zero is found. Add current row index + 1 to the result to count zeros and move on to the next column. In the end, return the result.

Algorithm

1. Start from the bottom-left corner of the matrix.

2. Decrease the row index till we reach 0.

3. Add the number of 0s in the current column to the result (current row index + 1) to count zeros and go to the next column.

4. Return the result.

Implementation

// Program to count Zeros in a row wise and column wise sorted matrix
#include <iostream>
using namespace std;
// size of the square matrix
#define A 3
 
int ZeroCounter(int mat[A][A])
{
    // start from bottom-left corner
    int m = A - 1, n = 0;
 
    // declaring result counter
    int ctr = 0;
 
    while (n < A)
    {
        //Continue until you find a 0
        while (mat[m][n])
 
            // if no zero is found in current column,
            // move to the next column
            if (--m < 0)
                return ctr;
 
        // count zeros of current column to the result variable
        ctr += (m + 1);
 
        // move to the next column
        n++;
    }
    return ctr;
}
 
// Driver Program
int main()
{
    int matrix[A][A] =
    {
        { 0, 0, 0},
        { 0, 0, 1},
        { 0, 1, 1}
    };
 
    cout << ZeroCounter(matrix);
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

3

Time Complexity

As the solution takes a single path from the bottom-left corner to the top or right edge of the matrix to count zeros, the time complexity is O(n).

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.

Also see,  Rabin Karp Algorithm