Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Rows and columns are nonincreasing. At the top-right corner of the unprocessed region, a negative value makes every value below it in that column negative. A nonnegative value means every remaining value to its left in that row is also nonnegative. Either observation eliminates a whole column or row.

Approach

Start at the top-right cell. If it is negative, add the number of rows from the current row to the bottom and move left. Otherwise move down. Continue until leaving the matrix. Each counted column segment is disjoint from earlier ones, and zero follows the nonnegative branch, so it is never counted.

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        r, c = 0, m - 1
        res = 0

        while r < n and c >= 0:
            if grid[r][c] < 0:
                res += n - r
                c -= 1
            else:
                r += 1

        return res

Complexity analysis

For R rows and C columns, the staircase pointers move down at most R times and left at most C times. Time is O(R + C) and auxiliary space is O(1).