# Count Negative Numbers in a Sorted Matrix: Staircase Search

Source: https://www.techinterview.org/post/3233459698/amazon-interview-question-count-negative-integers-in-matrix/
Updated: 2026-04-27 · techinterview.org

## Count Negative Numbers in a Sorted Matrix: Staircase Search and Binary Search

Counting negative numbers in a row-and-column-sorted matrix (LeetCode #1351) is a classic Amazon-flavored interview question. The matrix is sorted in non-increasing order both row-wise and column-wise, which means negatives cluster in the bottom-right. The naive O(n×m) scan works but misses the structural insight; the elegant O(n+m) staircase-search approach is what interviewers expect. This guide covers all three standard approaches with working code, the staircase intuition, and the variations interviewers ask.

## Problem Statement

Given an m×n matrix where each row and each column is sorted in non-increasing order, return the number of negative numbers.

Examples:


```
matrix = [
  [4, 3, 2, -1],
  [3, 2, 1, -1],
  [1, 1, -1, -2],
  [-1, -1, -2, -3]
]
→ 8 (count of negative entries)
```


Examples:

- `[[3, 2], [1, 0]]` → 0 (no negatives)

- `[[-1, -1], [-1, -1]]` → 4 (all negative)

## Approach 1: Brute Force (O(n×m))

Iterate every cell and count.


```
def count_negatives_brute(grid: list[list[int]]) -> int:
    """O(n*m) time, O(1) space."""
    return sum(1 for row in grid for x in row if x < 0)
```


Acceptable as a warm-up, especially for small matrices. Interviewers will push for O(n+m) or O(n log m).

## Approach 2: Staircase Search (Standard Answer, O(n+m))

Start at the top-right corner. The cell value tells you whether to move left (positive — count of negatives in this row to the right is zero) or down (negative — count this entry and all entries to its right).


```
def count_negatives(grid: list[list[int]]) -> int:
    """O(n + m) time — staircase from top-right."""
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    row, col = 0, cols - 1
    count = 0
    while row < rows and col >= 0:
        if grid[row][col] < 0:
            # All entries below are also negative due to column sort
            count += rows - row
            col -= 1
        else:
            row += 1
    return count


# Test
matrix = [
    [4, 3, 2, -1],
    [3, 2, 1, -1],
    [1, 1, -1, -2],
    [-1, -1, -2, -3]
]
print(count_negatives(matrix))  # 8
```


**Complexity:** O(n+m) time, O(1) space. Each iteration moves either left or down; total moves bounded by rows + cols.

### Why staircase works

The matrix is sorted decreasing left-to-right and top-to-bottom. At any cell:

- If the cell is negative, every cell *below* in the same column is also negative (because column is sorted decreasing). Count those (`rows - row`) and move left.

- If the cell is non-negative, no cell *to its left* in the same row is negative (because row is sorted decreasing — wait, decreasing means left is larger than right, so right side is more-negative; we should clarify direction).

Note: the convention can be either non-increasing or non-decreasing depending on the problem. LeetCode #1351 uses non-increasing (left and top are largest). The algorithm above matches that convention. For non-decreasing matrices, start at the bottom-right or top-left and adjust the move direction.

## Approach 3: Binary Search Per Row (O(n log m))

For each row, binary-search for the first negative. The count of negatives in that row equals (cols - first_negative_index).


```
from bisect import bisect_left

def count_negatives_binary(grid: list[list[int]]) -> int:
    """O(n log m) time."""
    if not grid or not grid[0]:
        return 0
    cols = len(grid[0])
    count = 0
    for row in grid:
        # Find first negative — row is sorted decreasing
        # Reverse perspective: find rightmost non-negative + 1
        # Use linear scan with binary search via bisect on reversed
        left, right = 0, cols
        while left < right:
            mid = (left + right) // 2
            if row[mid] < 0:
                right = mid
            else:
                left = mid + 1
        count += cols - left
    return count
```


**Trade-off:** O(n log m) is between brute force and staircase. For matrices where one dimension is much larger, this can be competitive. For square matrices, staircase wins.

## Common Variations

### Search a row-and-column-sorted matrix

(LeetCode #240) Same staircase pattern, but searching for a target. Move left if current is greater than target; move down if smaller. O(n+m) time.


```
def search_matrix(matrix: list[list[int]], target: int) -> bool:
    """Staircase search for target."""
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False
```


### Kth smallest in a sorted matrix

(LeetCode #378) Different problem — uses min-heap or binary search on values. Not a staircase problem directly; the structure is different.

### Count of inversions in an array

Different problem family. Merge-sort variant or Fenwick tree, not staircase.

### Count cells with property X in a sorted grid

Generalize: any property where the sortedness implies a monotonic boundary admits a similar staircase approach. "Count cells < threshold" or "count cells in range [a, b]" are both staircase-amenable.

## Common Mistakes

- **Confusing the sort direction.** Some problems have non-increasing matrices, others non-decreasing. Confirm with the interviewer or read the prompt carefully. The algorithm structure is the same; the move directions differ.

- **Starting from the wrong corner.** For non-increasing matrices, start top-right (smallest is bottom-right). For non-decreasing, start top-right or bottom-left. Each sortedness convention has two valid starting corners; the other two corners don't yield a clean staircase.

- **Off-by-one when counting.** When you find a negative at `grid[row][col]`, the count of negatives in column `col` from row `row` downward is `rows - row`, not `rows - row + 1` or `rows - row - 1`. Verify with a small example.

- **Using brute force unconsciously.** Recognizing the sortedness structure is the whole point. Brute force is acceptable as a warm-up but missing the structural insight signals weakness.

- **Quadratic accident with reset.** Some bad implementations reset the column pointer to `cols - 1` at each row, making the algorithm O(n × m). The pointer must persist across iterations for the staircase to work.

## Frequently Asked Questions

### What's the expected interview answer?

  Staircase search starting from the top-right corner. O(n+m) time, O(1) space. Walk through the algorithm with a small example. Mention brute force as a warm-up and binary-search-per-row as a middle ground. Strong candidates explain why the staircase works (sortedness implies monotonic boundary; one move per step bounds total operations).

### Can the staircase approach generalize?

  Yes — to any matrix where the sortedness gives you monotonic boundaries between regions. "Count cells less than threshold" or "search for a specific value" both work. The pattern requires that comparing the current cell with the target gives a clear "go left" or "go down" answer; matrices with weaker structure don't admit it.

### What if the matrix is sorted only by row, not by column?

  Different problem. Without column sort, you can binary-search each row independently for O(n log m). Without row sort but with column sort, transpose and apply the same. Without either, you must scan all cells in O(n × m). The structural assumptions matter; verify them.

### Does this work for matrices with duplicates?

  Yes — the algorithm doesn't care about distinctness, only ordering. Duplicates don't break the staircase invariant. The count is correct in either case.

### What's the most common follow-up?

  "Search the matrix for a specific value" (LeetCode #240). Same staircase pattern, with comparison against the target instead of zero. Strong candidates anticipate this and write the variation when prompted.

See also: [Two Sum: Find a Pair in an Array](/post/3233459633/sum-up-a-pair-in-array/) • [Right Rotate an Array by K Elements](/post/3233459583/right-rotate-an-array-by-k-elements/) • [Missing or Duplicate Number in an Array](/post/3233459624/missing-or-duplicate-number-in-an-array/)