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

- Traverse each row one by one
- Do a Binary search to find the first negative element index
- Subtract the length of row by index to find the total number of a negative number, because elements are arranged in descending order
- 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 ))
```