Matrix: Given a matrix, count zero in row wise and column wise matrix

Coding Interview Questions

1 min read

Problem Statement:

You are given a 2D matrix of size n * n where all the elements are 0 or 1.

They are sorted in ascending order.

You need to count the number of 0 present in whole of the matrix.

Example:

Input:

0, 0, 0, 0
1, 1, 1, 1
0, 0, 1, 1
1, 1, 1, 1

Output:

6

Solution Explanation:

Solution is very simple.

If a row starts with 1, then move to the next row.

If row starts with 0, then increment the count and move to the next element.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


int solution(const vector<vector<int>>& mat) {

    int n = mat.size();    
  
    int row = n - 1, col = 0;
    int count = 0;          

    while (col < n) {
      
        while (row >= 0 && mat[row][col]) {
            row--;
        }

        count += (row + 1);

        col++;
    }

    return count;
}

int main() {
    vector<vector<int>> mat = {
        { 0, 0, 0, 0 },
        { 1, 1, 1, 1 },
        { 0, 0, 1, 1 },
        { 1, 1, 1, 1 }
    };

    cout << solution(mat);

    return 0;
}