Count Negative Numbers in a Sorted Matrix

main.md

Question

Approach

I take advantage of the fact that the matrix is sorted in non-increasing order both row-wise and column-wise. Instead of checking every value, I start from the bottom-left corner of the grid. If the current value is negative, then I know every element to its right in that row must also be negative, so I add all of them to my count at once and then move one row up. But if the current value is non-negative, then I move one column to the right to look for negatives. I keep doing this until I either run out of rows or columns, and by the end I’ll have counted all negative numbers efficiently.

Implementation

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c = m - 1, 0
        count = 0
        
        while r >= 0 and c < n:
            if grid[r][c] < 0:
                count += (n - c) 
                r -= 1        
            else:
                c += 1  
        
        return count

Complexities

• Time: O(m + n)
• Space: O(1)