Count Negative Numbers in a Sorted Matrix

Problem Description

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Key Insights

• The matrix is sorted in non-increasing order, meaning each row and column is sorted such that larger values appear first.
• A systematic approach can be used to efficiently count negative numbers without checking every element.
• By starting from the bottom-left corner of the matrix, we can optimally navigate through the matrix based on the values encountered.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of rows and m is the number of columns.
Space Complexity: O(1) as we are using only a fixed amount of extra space.

Solution

We will utilize a two-pointer technique starting from the bottom-left corner of the matrix. The idea is to move right if the current number is negative (to count all negatives in that column) or move up if the current number is non-negative. This approach ensures we efficiently traverse the matrix without checking every single element.

1. Start at the bottom-left corner of the matrix.
2. Initialize a counter for negative numbers.
3. While within the bounds of the matrix:
   • If the current number is negative, increment the counter and move right (since all numbers above are also negative).
   • If the current number is non-negative, move up to check the next row.

This allows us to count all negative numbers in a single pass through the matrix.

Code Solutions