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

&nbsp;
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


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 100
	-100 &lt;= grid[i][j] &lt;= 100


&nbsp;
Follow up: Could you find an O(n + m) solution?
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0

        for i in grid:
            low = 0
            high = len(i) - 1

            while low <= high:
                mid = (low+high)//2
                if i[mid] < 0:
                    high = mid - 1
                elif i[mid] >= 0:
                    low = mid + 1
            count += (len(i) - low)
        return count
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length ;
        int n = grid[0].length ;
        int c = 0;
        int count = 0;
        int r = m-1;
        while( r >= 0 && c < n ) {
            if (grid[r][c] < 0 ) {
                r--;
                count += n - c;
            } else{
                c++;
            }
        }
        return count;
    }
}
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0; for (auto hehe : grid) for (int i : hehe) if (i < 0) ans++; return ans;
    }
};
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function(grid) {
  
    const m = grid.length
    const n = grid[0].length
    
    // for each row we need to find location of first negative
    // all columns past that are negative
    // also for next row search stops before
    // location of current first negative because 
    // all numbers below current are also lesser (negative) 
    
    function binSearch(start,end, arr){
        
        while(start<=end){
            let mid = start + ((end-start)>>1)
            if(arr[mid] < 0)
                end = mid - 1
            else 
                start = mid + 1
        }
        return arr[end]<0 ? end : end + 1
    }
    
    
    
    let ans = 0
    let searchTill = n-1
    for(let i=0;i<m;i++){
        
        if(searchTill<0){ 
            // last row found 0 in first column
            ans += n
            continue;
        }
        
        let firstNegative = binSearch(0,searchTill, grid[i])
        searchTill = firstNegative - 1
        ans += (n - firstNegative)
    }
    return ans
};
Count Negative Numbers in a Sorted Matrix