Count Negative Numbers in a Sorted Matrix in C++

We are going to solve the problem of counting negative numbers in a sorted matrix and learn about the concepts and algorithm used. Then we will see its implementation in C++.

Problem description

Return the number of negative numbers in grid. Given a n x m matrix grid which is sorted in non-increasing order both row-wise and column-wise, where n=number of rows and m=number of columns.

Example 1:

Input:

 grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Output:

 8

Explanation:

There are 8 negatives numbers in the matrix.

Example 2:

Input:

 grid = [[3,2],[1,0]]

Output:

 0

Example 3:

Input:

 grid = [[1,-1],[-1,-1]]

Output:

 3

Example 4:

Input:

 grid = [[-1]]

Output:

 1

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m,n <= 100
• -100 <= grid[i][j] <= 100

Approach

So according to the question, we are given a matrix and we had to count the total number of negative numbers and it is sorted in non-decreasing order both row-wise and column-wise. The first approach which comes to our mind is traversing the whole array and keep the count of negative numbers we encounter and return that. Its time complexity will be O(n*m) where n,m are the number of row and column respectively, Then we will be going to improve its time complexity by using a Binary search algorithm.

Binary search 

In this algorithm, we search for an element in a sorted array by keep on dividing the search interval to its half begin with an interval covering the whole array. If the value of the search element is less than the mid element then narrow the search interval to the lower half and discard the interval after the mid element and if the search element is greater than the mid element then narrow it to the upper half discarding the lower half. Repeatedly check until the value is found or the interval is empty.

Below is the C++ code:

int binsearch(int arr[], int l, int r, int x) // l is low value, r is high value and x is the element to be searched 
{ 

 while (l <= r)
{
 int m = l + (r - l) / 2; // calculating mid value 

 if (arr[m] == x)  // Check if x is present at mid
 return m; // If x greater, ignore left half 

 if (arr[m] < x) 
 l = m + 1; // If x is smaller, ignore right half 

 else
 r = m - 1; 

} 
// if element is not present then return -1 indicating x is not present in array 
return -1;
}

We will be using the same algorithm in our code to improve the time complexity.

Implementation

#include<iostream>
#include<vector>
using namespace std;
int countNegatives(vector<vector<int> >& grid) {
        int cnt=0;
        int n=grid.size();
        int m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                if(grid[i][j]<0)
                 cnt++;
        }
        return cnt;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int> >grid(n,vector<int>(m));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>grid[i][j];
    }
    cout<<countNegatives(grid);

return 0;
}

Now can we improve the time complexity of the above code? Yes, we can as in question it is mentioned that every row is sorted in non-increasing order so that means all negative number exists in a row after all positive numbers, so we need to just find the first negative number in a row and we can determine the total negative numbers in that row. Then for every row, we can calculate the same and keep the total in a variable and return that. For finding the first negative element position we can use the binary search algorithm. Now we have optimized the time complexity from O(n*m) to O(nlogm).

Implementation

#include<iostream>
#include<vector>
using namespace std;
int countNegatives(vector<vector<int> >& grid) {
       int cnt=0;
        for(int i=0;i<grid.size();i++)
        {
            vector<int>vec=grid[i];
            int m=grid[i].size();
            int l=0,h=m-1;
            int ans=m;
            while(l<=h){
                int mid=l+(h-l)/2;
                if(vec[mid]<0) // if negative element found in an row we decrement the high value as we  need to find the first negative value position
                {
                    ans=min(ans,mid);
                   h=mid-1;
                }
                else
                    l=mid+1;
            }
            cnt+=(m-ans);//cnt keeps the total of negative value present in matrix
        }

        return cnt;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int> >grid(n,vector<int>(m));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>grid[i][j];
    }
    cout<<countNegatives(grid);

return 0;
}

Sample case 

For the test case grid = [ [4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3] ] total negative elements present in row 1 is 1,  row 2 is 1, row 3 is 2, row 4 is 4. So total negative values are 1+1+2+4=8.

Hope you understand the implementation and algorithm used! Thank you.