Count Negative Numbers in a Sorted Matrix — Staircase and Binary Search [LC 1351]

Problem Statement#

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

Constraints:

• m == grid.length, n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100
• Each row and column is sorted in non-increasing order

Input:  grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8

Input:  grid = [[3,2],[1,0]]
Output: 0

Why This Problem Matters#

LC 1351 is an easy problem that teaches two important algorithmic ideas: the staircase walk (O(m+n)) and binary search per row (O(m log n)). Both exploit the sorted structure to beat the naive O(mn) scan.

The staircase walk is the same technique used in LC 240 (Search a 2D Matrix II) — start from a corner where one direction increases and another decreases, allowing you to eliminate a full row or column at each step. Understanding why the bottom-left (or top-right) corner is the right starting point is the key insight.

Google and Amazon ask this problem as a warm-up to verify that candidates think about sorted structure rather than brute-force scanning.

The Core Insight#

Staircase approach (O(m+n)): Start at the top-right corner (row 0, last column). The matrix is sorted in non-increasing order in both directions, so from the top-right:

• If grid[r][c] < 0: all elements below in column c are also negative (column is non-increasing downward). Add m - r to count, then move left (c--) to find the next boundary.
• If grid[r][c] >= 0: this cell is non-negative, so move down (r++).

Each step either advances r or retreats c, so the walk takes at most m + n steps.

Binary search approach (O(m log n)): For each row, binary search for the first negative element. Count = n - first_negative_index.

Visual Dry Run#

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Start at top-right: r=0, c=3

Solution (Optimal)#

class Solution:
    def countNegatives(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c = 0, n - 1  # start at top-right corner
        count = 0
 
        while r < m and c >= 0:
            if grid[r][c] < 0:
                # All elements in column c, rows r..m-1 are negative
                count += m - r
                c -= 1  # move left to next column
            else:
                r += 1  # move down to next row
 
        return count

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let r = 0, c = n - 1;
    let count = 0;
 
    while (r < m && c >= 0) {
        if (grid[r][c] < 0) {
            count += m - r;  // all rows below (inclusive) in column c are negative
            c--;
        } else {
            r++;
        }
    }
 
    return count;
};

Time: O(m + n) — at most m + n steps total Space: O(1) — only pointer variables

Binary search alternative (O(m log n)):

import bisect
 
def countNegatives(grid):
    count = 0
    for row in grid:
        # bisect_left finds the first index where 0 would be inserted
        # in the reversed row (which is sorted ascending for negatives)
        # Equivalently, find first negative in non-increasing row
        lo, hi = 0, len(row)
        while lo < hi:
            mid = (lo + hi) // 2
            if row[mid] < 0:
                hi = mid
            else:
                lo = mid + 1
        count += len(row) - lo
    return count

Common Mistakes#

• Starting at the top-left instead of top-right — from top-left, both moving right and moving down increase the value, so you cannot eliminate a direction.
• Using grid[r][c] <= 0 instead of < 0 — zero is not negative and should not be counted.
• In the staircase, forgetting to add m - r (counting all rows below, not just the current row).
• In binary search per row, confusing non-increasing order with non-decreasing — the rows are non-increasing, so the first negative is the first element less than 0.

Interview Tips#

• Mention both approaches: staircase (O(m+n)) and binary search per row (O(m log n)) — interviewers appreciate knowing you see multiple options.
• The staircase is the preferred answer because it uses the column-sorted property too; binary search per row ignores the column structure.
• This is the same staircase as LC 240 — if you've seen that problem, state the connection explicitly.

Follow-up Questions#

• LC 240 (Search 2D Matrix II): Uses the same staircase from top-right to find a target in O(m+n).
• What if you need the coordinates of all negative elements? Collect (r, c) pairs instead of incrementing a count — still O(m+n).
• What if the matrix is sorted differently (e.g., non-decreasing)? Adjust the staircase direction: start bottom-left, move up when negative, move right when non-negative.
• Can you do better than O(m+n)? No — you must inspect at least the boundary between positive and negative, which can span up to m + n positions.

Key Takeaways#

• LC 1351 has two valid solutions: staircase O(m+n) and binary search per row O(m log n) — knowing both demonstrates depth.
• The staircase starts at the top-right corner where moving left decreases the value and moving down increases it, enabling row or column elimination at each step.
• When grid[r][c] < 0: add m - r to count (all elements below in the column are also negative) and move left.
• When grid[r][c] >= 0: the current row element is non-negative, so move down.
• This is the same staircase walk used in LC 240 (Search 2D Matrix II) — the two problems share the same core technique.
• Binary search per row exploits only row-sorted order (O(m log n)); the staircase exploits both row and column order (O(m+n)).
• The column-sorted property is what gives the staircase its advantage over binary-search-per-row — always leverage all available sorted structure.