Matrix: Given a matrix, check if the matrix is sparse or not

Problem Statement:

You are given a 2D matrix with n * m size, you need to check if the matrix is sparse or not.

A matrix is called as sparse if most of the values are 0.

i.e the count of number of 0’s is more than half of the elements in the matrix.

Example:

Input:

 1 0 2
 0 0 3
 4 0 0

Output : Yes

Solution Explanation:

Solution is very simple.

You need to traverse the matrix and count the total number f zero.

If the count is more than (m*n)/2 then return true.

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

Code Solution

#include <iostream>
using namespace std;

const int MAX = 100;

bool solution(int array[][MAX], int m, int n)
{
    int count = 0;

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (array[i][j] == 0)
                ++count;

    return (count > ((m * n) / 2));
}

int main()
{
    int array[][MAX] = { { 1, 0, 2 }, 
                         { 0, 0, 3 }, 
                         { 4, 0, 0 } };

    int m = 3;
    int n = 3;

    if (solution(array, m, n))
        cout << "True";
    else
        cout << "False";
}

Output

True