Solution: Count Negative Numbers in a Sorted Matrix

Statement

Given a matrix grid of size $m \ * \ n$, where each row and column is sorted in non-increasing order, find and return the total count of negative numbers in the matrix.

Constraints:

• $m$ $==$ grid.length

• $n$ $==$ grid[i].length

• $1\leq$ $m$, $n$ $\leq 1000$

• $-100 \leq$ grid[i][j] $\leq 100$

Solution

This algorithm uses the matrix’s sorted structure, where each row and column is sorted in non-increasing order. In such a matrix, if there is a negative number in a row, all elements to its right will also be negative. Similarly, in the rows below, the first negative number will appear at the same position or further to the left.

To count the negative numbers, the algorithm starts from the right-most element of each row and moves left until it finds the first positive number. When a positive number is found, all elements to its right are guaranteed to be negative. For subsequent rows, instead of starting from the rightmost element again, the algorithm begins searching from the index found in the previous row to optimize the search process.

The algorithm to solve this problem is as follows:

1. Initialize a variable count to 0 to keep track of the total number of negative numbers.

2. Let n be the number of columns in the grid (n = len(grid[0])).

3. Initialize a variable current_index with the value n - 1 to store the index of the left-most negative number in a row.

4. For each row in the matrix:

   1. Start from current_index and move to left (i.e., decrement current_index) while the current element is negative and the beginning of the row has not been reached.

   2. Once a positive number is found, count all the negative numbers to its right using the formula n - (current_index + 1). Add this count to the total count.

5. After processing all the rows, the value of count will represent the total number of negative numbers in the matrix.

Let’s look at the following illustration to get a better understanding of the solution: