Count Negative Numbers in a Sorted Matrix: Staircase Search

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

See also: Two Sum: Find a Pair in an Array • Right Rotate an Array by K Elements • Missing or Duplicate Number in an Array

[-5, -4, -3,  1]
[-3, -2,  0,  2]
[-1,  0,  1,  3]
[ 1,  2,  3,  4]

function countNegatives(matrix) {
    if (!matrix || matrix.length === 0) return 0;

    let rows = matrix.length;
    let cols = matrix[0].length;
    let count = 0;

    // Start at bottom-left corner
    let row = rows - 1;
    let col = 0;

    while (row >= 0 && col < cols) {
        if (matrix[row][col] < 0) {
            // All elements above in this column are negative
            count += row + 1;
            col++;  // Move right
        } else {
            // Current element is non-negative
            row--;  // Move up
        }
    }

    return count;
}

// Test
const matrix1 = [
    [-5, -4, -3,  1],
    [-3, -2,  0,  2],
    [-1,  0,  1,  3],
    [ 1,  2,  3,  4]
];

console.log(countNegatives(matrix1));  // 6

const matrix2 = [
    [-3, -2, -1],
    [-2, -1,  0],
    [-1,  0,  1]
];

console.log(countNegatives(matrix2));  // 6 (all in upper-left)

function countNegativesBinary(matrix) {
    let count = 0;

    for (let row of matrix) {
        // Binary search for first non-negative
        let left = 0;
        let right = row.length - 1;
        let firstNonNeg = row.length;

        while (left <= right) {
            let mid = Math.floor((left + right) / 2);

            if (row[mid] < 0) {
                left = mid + 1;
            } else {
                firstNonNeg = mid;
                right = mid - 1;
            }
        }

        count += firstNonNeg;
    }

    return count;
}

console.log(countNegativesBinary(matrix1));  // 6