DSA Tracker

Visualize

Count Negative Numbers in a Sorted Matrix

Staircase walk from the bottom-left corner — O(m+n), no extra memory

time O(m+n)space O(1)

Scanning every cell works but ignores the sorting entirely. Start at the bottom-left instead: moving right only ever increases the value and moving up only ever increases it too, so the bottom-left corner is the smallest value reachable by that walk. When the current cell is negative, the whole rest of that row is negative (rows are non-increasing), so count the slice in one step and move up to a row that can't repeat it. When it isn't negative, move right — nothing to the left could have been negative either, since it would already have been found. Each cell is visited at most once, so the walk is O(m+n).

Details

Animated on: matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] — every row and column sorted non-increasing. Count the negative entries.

Problem:Count Negative Numbers in a Sorted MatrixEasy

Staircase walk from the bottom-left corner — O(m+n), no extra memory

step 1 / 9

4x4 matrix, sorted non-increasing along every row and column

Start at the bottom-left corner (3,0) — moving right only increases the value, moving up only increases it too, so this cell is the smallest reachable by that walk.

Pseudocode
1FUNCTION countNegatives(matrix):
2  n <- LENGTH(matrix[0])
3  row <- LENGTH(matrix) - 1
4  col <- 0
5  count <- 0
6  WHILE row >= 0 AND col < n:
7    IF matrix[row][col] < 0:
8      count <- count + (n - col)
9      row <- row - 1
10    ELSE:
11      col <- col + 1
12  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Start at the bottom-left corner (3,0) — moving right only increases the value, moving up only increases it too, so this cell is the smallest reachable by that walk.
  2. matrix[3][0] = -1 is negative, and the row is sorted non-increasing, so everything right of it on row 3 is negative too: +4, count = 4. Move up to row 2 — that row can't repeat this one.
  3. matrix[2][0] = 1 is not negative, so nothing here counts. Move right to column 1 in search of the first negative on this row.
  4. matrix[2][1] = 1 is not negative, so nothing here counts. Move right to column 2 in search of the first negative on this row.
  5. matrix[2][2] = -1 is negative, and the row is sorted non-increasing, so everything right of it on row 2 is negative too: +2, count = 6. Move up to row 1 — that row can't repeat this one.
  6. matrix[1][2] = 1 is not negative, so nothing here counts. Move right to column 3 in search of the first negative on this row.
  7. matrix[1][3] = -1 is negative, and the row is sorted non-increasing, so everything right of it on row 1 is negative too: +1, count = 7. Move up to row 0 — that row can't repeat this one.
  8. matrix[0][3] = -1 is negative, and the row is sorted non-increasing, so everything right of it on row 0 is negative too: +1, count = 8. Row 0 was the last one to check.
  9. Row went past the top (row = -1), so there is nothing left to check. count = 8 negatives.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Negative Numbers in a Sorted Matrix in the editorAll Matrix problemsBack to roadmap