# Binary Search Problem |LeetCode Problem – 1|Easy

## Count Negative Numbers in a Sorted Matrix

Problem – Given a `m * n` matrix `grid` which is sorted in non-increasing order both row-wise and column-wise.  Return the number of negative numbers in `grid` using Binary search in this problem

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 number 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

## Solution

According to size, if we go in linear fashion, that is, Check each cell of matrix one by one the time complexity is O (m*n)  which is affordbale if m and n less then 100

But if we try to do it in O(m*log(n)) time, We have to use Binary Search, which is better approach.

#### Linear Search Solution

Algorithm –

Simply traverse one by one each cell of matrix and increase count if the value is negative

``````int countNegatives(vector<vector<int>>& grid) {

int ans = 0;
for(int i =0;i<grid.size();i++)
{
for(int j = 0;j<grid[i].size();j++)
if(grid[i][j]<0)
ans++;

}
return ans;
}
Time Complexity – O(no of rows* no of column)
``````

#### Binary Search Solution

As we know, Binary search is a divide and conquer algorithm, so, we are going to focus on dividing each row of the array in this problem

1. Traverse each row one by one
2. Do a Binary search to find the first negative element index
3. Subtract the length of row by index to find the total number of a negative number, because elements are arranged in descending order
4. Repeat Until any row left
``````class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {

int ans = 0;
for(int i =0;i<grid.size();i++)
{
ans+=binarySearch(grid[i]); // Traversing each row one by one

}
return ans;

}

int binarySearch(vector<int> &bs)
{
int  l = 0;
int  r = bs.size()-1;

while(l<=r)
{
int mid = (l+r)/2;
if(bs[mid]<0)
{                    // for finding negative element

r = mid-1;
}
else
l = mid+1;

}
if(l<bs.size() && bs[l]<0)
return bs.size()-l;   // return number of negative element
else
return 0;

}
};
Time Complexity  = O(no of rows * log( max of column ))
`````` Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

1. waterfallmagazine.com says:
2. Carole says: