Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix is LeetCode 1351, and it is one of the cleanest introductions to the staircase traversal pattern on a sorted matrix. You are given an m x n matrix grid where both rows and columns are sorted in non-increasing order. Your job is to count how many negative numbers are in the matrix.

The problem

Given an m x n matrix grid sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]. The answer is 8 because there are eight negative numbers in the matrix.

Notice the structure. Every row is sorted from largest to smallest (left to right), and every column is sorted from largest to smallest (top to bottom). That double-sorted property is the key to solving this faster than scanning every cell.

The approach

There are three ways to tackle this problem, from simplest to most efficient.

Brute force: Loop through every cell and check if it is negative. This works but ignores the sorted structure entirely. Time: O(m * n).

Binary search per row: Since each row is sorted in non-increasing order, you can binary search for the first negative number in each row. Everything to its right is also negative, so you add cols - index to your count. You do this for all m rows. Time: O(m log n).

Staircase traversal: Start at the top-right corner. If the current value is negative, then everything below it in that column is also negative (because columns are sorted in non-increasing order). Add all those cells to your count and move left. If the current value is non-negative, move down to the next row. Each step either moves left or down, so you take at most m + n steps total. Time: O(m + n).

The staircase approach is the most elegant. You are exploiting the fact that the matrix is sorted in both dimensions.

The code

Here is the optimal O(m + n) Python solution:

def countNegatives(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    row = 0
    col = cols - 1

    while row < rows and col >= 0:
        if grid[row][col] < 0:
            count += rows - row
            col -= 1
        else:
            row += 1

    return count

You start at the top-right corner with row = 0 and col = cols - 1. At each step, you check grid[row][col]:

• If it is negative, every cell from row down to the last row in this column is also negative. That is rows - row cells. Add them to count and move left by decrementing col.
• If it is non-negative, there are no negatives above this point in the column (they would need to be even larger, so they cannot be negative). Move down by incrementing row.

The loop ends when you either fall off the left edge (col < 0) or the bottom edge (row >= rows).

Step-by-step walkthrough

Let's trace through grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]. Watch how the pointer zigzags from the top-right corner, moving left on negatives and down on non-negatives.

The pointer visited 7 cells and counted all 8 negatives. That is much better than checking all 16 cells. The path traces a staircase shape from the top-right corner toward the bottom-left.

Complexity analysis

All three approaches use O(1) extra space since you only need a few variables. The staircase traversal wins on time because each step eliminates an entire row or column from consideration, and you never revisit a cell.

For a 1000 x 1000 matrix, brute force checks up to 1,000,000 cells. Binary search checks about 1000 * 10 = 10,000. Staircase checks at most 2000. The difference matters at scale.

The building blocks

1. Staircase traversal on a sorted matrix

The pattern of starting at a corner and moving in two directions based on comparisons:

row = 0
col = cols - 1

while row < rows and col >= 0:
    if condition(grid[row][col]):
        # Exploit column ordering, move left
        col -= 1
    else:
        # Exploit row ordering, move down
        row += 1

This template applies to any matrix where rows and columns are sorted (either both ascending or both descending). You saw it in Search a 2D Matrix II (LeetCode 240), where you use it to find a target value. Here, you use it to count negatives. The only thing that changes between problems is what you do when you hit a match. The traversal pattern itself is identical.

2. Binary search on rows for the boundary

When a single row is sorted, you can binary search for the transition point between non-negative and negative values:

def first_negative(row):
    lo, hi = 0, len(row)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if row[mid] < 0:
            hi = mid
        else:
            lo = mid + 1
    return lo

This gives you the index of the first negative in a row. Everything from that index onward is negative. Running this on each row gives the O(m log n) approach. It is a good fallback if you forget the staircase pattern, and it also shows up in problems like "Find First and Last Position of Element in Sorted Array" (LeetCode 34).

Edge cases

• No negatives: grid = [[3,2],[1,0]]. The pointer walks down and right without ever hitting a negative. Returns 0.
• All negatives: grid = [[-1,-2],[-3,-4]]. At position (0, 1), everything below is negative, so count = 2. Move left. At (0, 0), count += 2. Returns 4.
• Single row: grid = [[5,3,-1,-3]]. Binary search or staircase both work. The pointer starts at col 3, finds -1 at some point, and counts from there.
• Single column: grid = [[5],[3],[-1],[-3]]. The pointer starts at (0, 0), moves down until it hits -1 at row 2, then counts rows - row = 2. Done.
• Single element: grid = [[-5]] returns 1. grid = [[5]] returns 0.
• Zeros in the matrix: grid = [[1,0,0,-1]]. Zero is not negative. The pointer correctly skips zeros and only counts -1.

From understanding to recall

The logic here is simple: start top-right, go left on negative, go down on non-negative. But in a timed setting, the details matter. Do you add rows - row or rows - row + 1? Do you start at col = cols - 1 or col = cols? Do you check < 0 or <= 0?

These are not conceptual questions. They are precision questions, and they trip people up when they are writing code under pressure. The fix is repetition. You write the staircase traversal from scratch today, again in two days, then again in a week. Each time, the boundary conditions feel more natural. After a few rounds, you do not think about whether it is rows - row or rows - row + 1. Your hands just type the right thing.

The staircase pattern also transfers directly to Search a 2D Matrix II. If you can write this solution from memory, you already know how to solve that medium-difficulty problem too.

Related posts

• Search a 2D Matrix - Binary search on a fully sorted matrix by treating it as a virtual 1D array
• Search a 2D Matrix II - The staircase search pattern applied to finding a target in a row-and-column sorted matrix
• Binary Search - The foundational binary search template that powers the per-row approach