Count Negative Numbers in a Sorted Matrix

Problem Statement

The task is to develop a function that can navigate through an m x n matrix of integers. This matrix is organized in such a way that both rows and columns are sorted in a non-increasing order. The primary goal of the function is to count and return the total number of negative numbers contained within the matrix. This has direct real-world applications where matrices are used to represent various types of data that can possess dual sorting, and a specific count of certain value types (negative numbers in this case) is required for further processing or decision-making.

Examples

Example 1

Input:

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

Output:

8

Explanation:

There are 8 negatives number in the matrix.

Example 2

Input:

grid = [[3,2],[1,0]]

Output:

0

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Approach and Intuition

Given that the matrix is sorted in non-increasing order both row-wise and column-wise, we can leverage this property to optimize the counting of negative numbers. Here's a logical approach to tackle this:

1. Understand Matrix Properties: Recognize that the top-right or bottom-left corner of the matrix can serve as a starting point for checking negative numbers efficiently. If you start from the top-right corner, the movement strategy can be outlined as follows: if a negative number is found, every element below in the same column is also negative (due to the column-wise sorting).

2. Efficiently Navigate through the Matrix:

   • Start from the top-right corner of the matrix.
   • If the number is negative, all the numbers below in that column are also negative (because the matrix is sorted in non-increasing order column-wise). Add all these numbers to the negative count and move left to check the next column.
   • If the number is non-negative, move downward to the next row while staying in the same column as the numbers to the left might still be negative.

3. Iterative Counting:

   • Initialize a counter for negative numbers.
   • Use two pointers or indices (one for rows and another for columns) to navigate through the matrix based on the conditions mentioned above.
   • Increment the counter appropriately as each negative number is identified.

4. End Condition:

   • The process can terminate early if the leftmost column or the bottommost row is reached without finding further negative numbers.

5. Edge cases:

   • Consider edge cases where the smallest matrix dimension is 1 (either 1 row or 1 column), or where there are no negative numbers at all.

By implementing the above method, the function can minimize the number of elements it needs to examine, thus enhancing efficiency particularly in larger matrices, making use of the sorted property to skip entire sections of the matrix that do not require examination.

Solutions

class Solution {
public:
    int countNegatives(vector<vector<int>>& matrix) {
        int negativeCount = 0;
        int columnCount = matrix[0].size();
        int negativeStartIndex = columnCount - 1;
    
        for (auto& eachRow : matrix) {
            while (negativeStartIndex >= 0 && eachRow[negativeStartIndex] < 0) {
                negativeStartIndex--;
            }
            negativeCount += (columnCount - (negativeStartIndex + 1));
        }
        return negativeCount;
    }
};