Count Negative Numbers in a Sorted Matrix

Intuition

Anchor a pointer at the bottom-left cell. If that cell is negative, then every cell to its right in the same row must also be negative because the row decreases left to right; you can add that whole remaining segment at once and move up a row. If the cell is not negative, moving right is pointless from here, so advance the column instead. Each step either climbs a row or shifts a column, so the pointer sweeps a monotone staircase across the grid.

Algorithm walkthrough

1. 1Set row to the last row index and col to 0, and initialize count to 0.
2. 2While row is valid and col is within bounds, look at grid[row][col].
3. 3If it is negative, add (cols - col) to count because the rest of that row is negative too, then decrement row.
4. 4Otherwise increment col to search further right in the higher rows.
5. 5When the walk finishes, count holds the number of negative values.

Implementation

from typing import List


class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        count = 0
        row, col = rows - 1, 0
        while row >= 0 and col < cols:
            if grid[row][col] < 0:
                count += cols - col
                row -= 1
            else:
                col += 1
        return count