Solution: Count Negative Numbers in a Sorted Matrix
Let’s solve the Count Negative Numbers in a Sorted Matrix using the Matrices pattern.
We'll cover the following
Statement
Given a matrix grid
of size
Constraints:
grid.length
grid[i].length
, grid[i][j]
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:
Initialize a variable
count
to0
to keep track of the total number of negative numbers.Let
n
be the number of columns in the grid (n = len(grid[0])
).Initialize a variable
current_index
with the valuen - 1
to store the index of the left-most negative number in a row.For each row in the matrix:
Start from
current_index
and move to left (i.e., decrementcurrent_index
) while the current element is negative and the beginning of the row has not been reached.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 totalcount
.
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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.