Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Count Negative Numbers in a Sorted Matrix

Count the negative numbers in a grid whose rows and columns are sorted in descending order, in O(rows + columns), with a staircase walk from a corner.

easyPattern: Matrix Search

Updated Medium read: 8 min read

Approaches at a glance

ApproachTimeSpace
Check every cellO(rows × columns)O(1)
Binary search each rowO(rows × log columns)O(1)
Staircase walkO(rows + columns)O(1)

The problem

You are given a grid of integers. Reading any row from left to right, the values never go up. Reading any column from top to bottom, the values never go up either. Equal neighbours are allowed. Return how many of the values are negative, that is, less than zero.

grid =
   6   3   1  -2
   4   2  -1  -3
   1   0  -4  -5
  -2  -3  -6  -8        →  9
 
grid =
   5   2
   1   0                →  0    (zero is not negative)
 
grid =
  -1  -4                →  2

Because large values sit at the top-left and small ones at the bottom-right, the negative numbers are all pushed towards the bottom-right corner. The three approaches below differ only in how much of that fact they use.

Approach 1: check every cell

Ignore the ordering, visit each cell and count the ones below zero.

JavaScript

function countNegativesBruteForce(grid) {
  let count = 0;
  for (const row of grid) {
    for (const value of row) {
      if (value < 0) count++;
    }
  }
  return count;
}

Python

def count_negatives_brute_force(grid):
    count = 0
    for row in grid:
        for value in row:
            if value < 0:
                count += 1
    return count

Time O(rows × columns). Space O(1). It is short and obviously right, which makes it a good reference to test the faster versions against. On a grid of 1,000 by 1,000 it reads a million cells.

Approach 2: binary search each row

Each row is sorted in descending order, so its negative numbers form one block at the right-hand end. Find where that block starts and the count for the row follows without looking at the rest: it is the number of columns minus the starting index.

Finding the start of the block is a binary search for a boundary, the same shape as Search Insert Position. The question asked of each middle cell is "is this negative?". The answers along a row run "no, no, …, yes, yes", and the search finds the first "yes".

JavaScript

// Index of the first negative value in a row sorted in descending order.
// Returns row.length when the row has no negative value.
function firstNegativeIndex(row) {
  let lo = 0;
  let hi = row.length;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (row[mid] < 0) {
      hi = mid;       // mid is negative: the block starts here or earlier
    } else {
      lo = mid + 1;   // mid is not negative: the block starts later
    }
  }
  return lo;
}
 
function countNegativesByRow(grid) {
  let count = 0;
  for (const row of grid) {
    count += row.length - firstNegativeIndex(row);
  }
  return count;
}

Python

# Index of the first negative value in a row sorted in descending order.
# Returns len(row) when the row has no negative value.
def first_negative_index(row):
    lo = 0
    hi = len(row)
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if row[mid] < 0:
            hi = mid      # mid is negative: the block starts here or earlier
        else:
            lo = mid + 1  # mid is not negative: the block starts later
    return lo
 
 
def count_negatives_by_row(grid):
    count = 0
    for row in grid:
        count += len(row) - first_negative_index(row)
    return count

For the row [4, 2, -1, -3] the first negative value is at index 2, so the row adds 4 - 2 = 2 to the count.

Time O(rows × log columns). Space O(1). This uses the order within each row but not the order down the columns: every row is searched from scratch, as if the row above had revealed nothing.

Approach 3: staircase walk

The columns are sorted too, and that links one row to the next. If a cell is negative, every cell below it in the same column is smaller or equal, so it is negative as well. That means the block of negative numbers can only start at the same column or further left as you move down the grid. The edge of the negative region is a staircase, which is easy to see with the negatives marked:

   6    3    1  [-2]
   4    2  [-1] [-3]
   1    0  [-4] [-5]
 [-2] [-3] [-6] [-8]

Start at the top-right corner and repeat one test:

  • The cell is negative. So is everything below it. Add the number of cells from here to the bottom of the column, then move one column left. That column is finished.
  • The cell is not negative. Everything to its left in this row is at least as large, so this row has no more negatives to offer. Move one row down.

JavaScript

function countNegatives(grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length;
  let row = 0;
  let col = grid[0].length - 1;
  let count = 0;
 
  while (row < rows && col >= 0) {
    if (grid[row][col] < 0) {
      count += rows - row;   // this cell and everything below it
      col--;
    } else {
      row++;
    }
  }
  return count;
}

Python

def count_negatives(grid):
    if not grid:
        return 0
    rows = len(grid)
    row = 0
    col = len(grid[0]) - 1
    count = 0
 
    while row < rows and col >= 0:
        if grid[row][col] < 0:
            count += rows - row  # this cell and everything below it
            col -= 1
        else:
            row += 1
    return count

Walkthrough

The four-by-four grid from the top of the page, with rows = 4:

row col Value Negative? Action count
0 3 -2 Yes Add 4 − 0 = 4, move left 4
0 2 1 No Move down 4
1 2 -1 Yes Add 4 − 1 = 3, move left 7
1 1 2 No Move down 7
2 1 0 No Move down 7
3 1 -3 Yes Add 4 − 3 = 1, move left 8
3 0 -2 Yes Add 4 − 3 = 1, move left 9
3 -1 col is off the grid: return 9 9

Seven cells read out of sixteen, and the gap widens as the grid grows. Each step moves either one row down or one column left and never back, so there are at most rows + columns steps.

Time O(rows + columns). Space O(1).

This is the counting form of the staircase walk in the matrix search pattern. The pattern page describes it for grids sorted in ascending order; here the order is descending, so the meaning of each move is worked out again from scratch rather than copied.

Comparing the approaches

Approach Uses row order Uses column order Time Cells read on a 1,000 × 1,000 grid, at most
Check every cell No No O(rows × columns) 1,000,000
Binary search each row Yes No O(rows × log columns) About 10,000
Staircase walk Yes Yes O(rows + columns) 2,000

All three use O(1) extra space. For a grid with very few rows and very many columns, binary searching each row can read fewer cells than the staircase, since rows × log columns is then smaller than rows + columns. When that matters, binary search along whichever side is longer. For grids that are roughly square, the staircase wins comfortably.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

const grid = [[6, 3, 1, -2], [4, 2, -1, -3], [1, 0, -4, -5], [-2, -3, -6, -8]];
console.log(countNegatives(grid)); // 9
console.log(countNegatives([[5, 2], [1, 0]])); // 0
console.log(countNegatives([[-1, -4]])); // 2
console.log(countNegativesByRow(grid)); // 9

Python

grid = [[6, 3, 1, -2], [4, 2, -1, -3], [1, 0, -4, -5], [-2, -3, -6, -8]]
print(count_negatives(grid))  # 9
print(count_negatives([[5, 2], [1, 0]]))  # 0
print(count_negatives([[-1, -4]]))  # 2
print(count_negatives_by_row(grid))  # 9

The comment after each line is the result you should see.

Common mistakes

  • Counting zero as negative. The test is value < 0. Writing <= 0 passes many tests and fails on any grid that contains a zero.
  • Adding one per negative cell in the staircase. The point of the walk is that a negative cell accounts for its whole column from that row down. Adding 1 and then moving left misses everything beneath it.
  • Adding row + 1 or col + 1 out of habit. In this problem the negatives lie below the current cell, so the amount to add is rows - row. Draw a three-by-three grid and check before trusting the formula.
  • Starting at the top-left. From there both moves lead to smaller values, so a non-negative cell does not say which way to go. Use the top-right or the bottom-left.
  • Copying an ascending-order staircase unchanged. This grid is sorted in descending order. The moves look similar but mean the opposite.

Original problem: LeetCode 1351: Count Negative Numbers in a Sorted Matrix