Count Negative Numbers in a Sorted Matrix

Share

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

Example 1
Input: [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] → Output: 8
Example 2
Input: [[3,2],[1,0]] → Output: 0

Solution Approach

Start from top-right corner. Move left if current is negative (count all below in this column), move down if positive.

  • r=0, c=n-1, count=0.
  • While r=0: if grid[r][c]<0: count+=m-r; c--; else r++.
Java
class Solution {
    public int countNegatives(int[][] grid) {
        int m=grid.length, n=grid[0].length, r=0, c=n-1, count=0;
        while (r<m && c>=0) {
            if (grid[r][c]<0) { count+=m-r; c--; }
            else r++;
        }
        return count;
    }
}
  • Time Complexity: O(M+N)
  • Space Complexity: O(1)