Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is the time complexity for traversing a matrix?
3.2.
Why is the time complexity of the above solution O(n)?
3.3.
Can we allocate a 2-dimensional array dynamically?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Zeros in a row wise and column wise sorted matrix

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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;
}

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the time complexity for traversing a matrix?

Traversing a 2D array takes O (N * M) time, where N is the number of rows and M is the number of columns.

Why is the time complexity of the above solution O(n)?

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

Can we allocate a 2-dimensional array dynamically?

A 2D array should be dynamically allocated in C++ using a single pointer. 

Conclusion

This article extensively discussed the problem to count zeros in a row wise and column wise sorted matrix and its time and space complexities.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Types of MatrixFind Good MatrixPrint MatrixMatrix is SymmetricSet Matrix Zeros.

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problemsinterview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

 

Happy Coding!

Previous article
Interchange elements of first and last rows in matrix
Next article
Given 1’s, 2’s, 3’s ……k’s Print them in ZigZag way
Live masterclass