Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix

What is this problem about?

The "Count Negative Numbers in a Sorted Matrix" coding problem asks you to find the total count of negative integers in an $m imes n$ matrix. The matrix has a special property: both its rows and columns are sorted in non-increasing order (from largest to smallest).

Why is this asked in interviews?

This is a classic "Easy" question used by Microsoft, Amazon, and Google to see if a candidate can move beyond a brute-force $O(m imes n)$ solution. It tests your ability to leverage the sorted property of a matrix to achieve a better time complexity, specifically $O(m + n)$.

Algorithmic pattern used

While you can use Binary Search on each row for an $O(m \log n)$ solution, the most efficient pattern is the Staircase Search or Two Pointers pattern. Starting from the bottom-left corner (or top-right), you can navigate the boundary between positive and negative numbers. If a number is negative, all numbers to its right in that row are also negative. You add that count and move up a row. If it's non-negative, you move right to find the first negative number.

Example explanation

Matrix:

[ [ 4,  3,  2, -1],
  [ 3,  2,  1, -1],
  [ 1,  1, -1, -2],
  [-1, -1, -2, -3] ]

1. Start at bottom-left: (3,0), value is -1.
2. Since -1 is negative, all 4 numbers in this row are negative. Count = 4. Move up to row 2.
3. At (2,0), value is 1 (Positive). Move right.
4. At (2,1), value is 1 (Positive). Move right.
5. At (2,2), value is -1 (Negative). Everything from here to the end of the row is negative (2 numbers). Total count = 4 + 2 = 6. Move up to row 1. ... and so on.

Common mistakes candidates make

A frequent mistake is not using the sorted property and just iterating through every element, which is inefficient. Another is getting the staircase logic backwards (moving left when you should move right) or hitting an infinite loop by not updating the row/column pointers correctly.

Interview preparation tip

Whenever you see a matrix that is "sorted by rows and columns," think about the Staircase Search. It's almost always the optimal way to find targets or boundaries in linear time relative to the sum of the dimensions.