Count Negative Numbers in Sorted Matrix — Row Binary Search

# Python — O(m+n) staircase
def countNegatives(grid):
    m, n = len(grid), len(grid[0])
    r, c = 0, n-1
    count = 0
    while r < m and c >= 0:
        if grid[r][c] < 0:
            count += m-r  # all elements below in this column
            c -= 1
        else:
            r += 1
    return count

// Java
public int countNegatives(int[][] grid) {
    int m=grid.length, n=grid[0].length, r=0, c=n-1, cnt=0;
    while (r<m&&c>=0) {
        if (grid[r][c]<0) { cnt+=m-r; c--; } else r++;
    }
    return cnt;
}