Count Negative Numbers in Sorted Matrix
An easy Matrix problem included in Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Matrix
- Sheets
- 1
- Core for
- 10 roles
- Platform
- LeetCode
The problem
Given an m-by-n matrix where each row and column is sorted in ascending order, count the number of negative numbers.
Example 1
- Input
- matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
- Output
- 8
Example 2
- Input
- matrix = [[3,2],[1,0]]
- Output
- 0
- Why
- No negative numbers in the matrix.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- Rows and columns sorted in non-increasing order
How to think about it
Updated 2026-09-09Rows and columns are sorted in descending order, so the bottom-left corner is the pivot. Moving right increases values, moving up decreases them. Each step either counts a full slice of negatives or moves past them, walking the matrix boundary in linear time.
Approaches, worst first
Scan every cell
time O(m*n) · space O(1)
Check each element against zero. Correct and simple, but ignores the sorting entirely. Every cell is visited regardless of how many negatives exist, wasting the structure of the input.
Staircase from bottom-left
time O(m+n) · space O(1)
Start at the bottom-left corner. If the current value is negative, every cell above in the same column is also negative because the column is descending, so count the slice and move up. Otherwise move right.
Binary search per rowWrite this one
time O(m log n) · space O(1)
For each row, binary search for the boundary between non-negative and negative values. Since rows are descending, negatives are on the right side. Counts the negatives in each row independently.
Where people lose marks · 3
- The matrix is sorted in non-increasing (descending) order, not ascending. The staircase starts at bottom-left, not top-right as the ascending version does. Starting in the wrong corner walks in the wrong direction.
- When the current value is negative, every cell from the current column to the right in this row is also negative because the row is descending. Counting n minus column is correct, but moving right would double-count since those cells are already accounted for.
- If the column index exceeds n while moving right, the loop must stop. Continuing past the boundary reads out of bounds and produces garbage results.
The theory behind it
Matrix — the ground this problem stands on. All Matrix problems
What Matrix is
A matrix is a flat grid of cells laid out in rows and columns, like a checkerboard or a spreadsheet. Each cell has an address made of two numbers: its row index going down and its column index going across. Because computer memory stores these rows one after another or as arrays of arrays, jumping straight to any individual cell takes the same tiny fraction of time no matter where it sits on the board.
When to reach for it
Reach for matrix techniques when the input is a two-dimensional grid, board, or map. Common prompts include walking through a maze, finding connected islands of land in water, rotating an image ninety degrees in place, or reading numbers in a spiral. Words like rows, columns, neighbors, adjacent squares, or diagonal lines are clear signs. It also appears in grid planning where each cell depends on the values above and to the left.
How the pattern works
Think of navigating the grid using directional coordinate offsets. Define row and column step arrays for moving up, down, left, and right. Always check that new row and column indices stay strictly between zero and the board boundaries before reading cell values. For spiral scans, track four boundary lines for top, bottom, left, and right, shrinking them inward after reading each side. When searching connected regions, mark visited cells directly or write a marker value into the cell to avoid looping.
What each operation costs
| Operation | Time |
|---|---|
| read or write cell by row and column | O(1) |
| visit every cell across m rows and n columns | O(m * n) |
| rotate square matrix in place | O(n^2) |
What usually goes wrong with Matrix
- Flipping row and column dimensions by mixing up grid height with grid width, causing index out of bounds crashes on rectangular grids where row and column counts differ.
- Reading neighbor cells without first confirming that the row and column coordinates are within valid bounds between zero and the board edges.
- Forgetting to update inner boundary limits during spiral traversal, which causes single-row or single-column matrices to print duplicate entries.
Which roles need this problem
Matrix is a core topic for these 10 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 7 more roles, including Frontend Engineer, Full-Stack Developer, Android Developer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Matrix problems
Problem set and role mapping as of .