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.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Check every cell | O(rows × columns) | O(1) |
| Binary search each row | O(rows × log columns) | O(1) |
| Staircase walk | O(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 → 2Because 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 countTime 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 countFor 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 countWalkthrough
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)); // 9Python
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)) # 9The comment after each line is the result you should see.
Common mistakes
- Counting zero as negative. The test is
value < 0. Writing<= 0passes 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 + 1orcol + 1out of habit. In this problem the negatives lie below the current cell, so the amount to add isrows - 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