1351. Count Negative Numbers in a Sorted Matrix

/*1351. Count Negative Numbers in a Sorted Matrix
Runtime: 1 ms, faster than 50.09% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 39.4 MB, less than 63.38% of Java online submissions for Count Negative Numbers in a Sorted Matrix.*/

class Solution {
    public int countNegatives(int[][] grid) {
      int count=0;
        for(int i=0;i<grid.length;i++)
            for(int j=0;j<grid[0].length;j++)
                if(grid[i][j]<0)
                    count++;
        
        
        return count;
        
    }
}


/* 1351. Count Negative Numbers in a Sorted Matrix
Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 39.2 MB, less than 78.44% of Java online submissions for Count Negative Numbers in a Sorted Matrix.*/

class Solution {
    public int countNegatives(int[][] grid) {
 int rows = grid.length, cols = grid[0].length; 
        int res = 0, lastNeg = cols - 1;
        for (int row = 0; row < rows; row++) {
            
            if (grid[row][0] < 0) {
                res+=cols;
                continue;
            }
            
            if (grid[row][cols - 1] > 0)
                continue;
           
            
            int l = 0, r = lastNeg;
            while (l <= r) {
                int m = l + (r - l)/2;
                if (grid[row][m] < 0) {
                    r = m - 1;
                } else
                    l = m + 1;
            }
            
            res += (cols - l); lastNeg = l;
        }
        return res;
    }
}