LeetCode 1351 · Binary search

Count Negative Numbers in a Sorted Matrix, explained with a picture

A staircase walk through freezing readings.

Binary search
▶ Watch it step by step

The problem

In a grid sorted in decreasing order along every row and every column, count the negative numbers.

Input:  4,3,2,−1 / 3,2,1,−1 / 1,1,−1,−2 / −1,−1,−2,−3
Output: 8

Picture it

Picture a staircase walk starting at the bottom-left. If the reading is negative, everything to its right in that row is negative too: count them all and step up. Otherwise step right. The walk never retraces, so it’s fast.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Staircase search from a corner: O(rows + cols).

Python solution

def count_negatives(grid):     # rows and columns decrease
    r, c = len(grid) - 1, 0
    count = 0
    while r >= 0 and c < len(grid[0]):
        if grid[r][c] < 0:
            count += len(grid[0]) - c
            r -= 1
        else:
            c += 1
    return count

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.