Given an `M × N` matrix, which is row-wise and column-wise sorted, count the total number of negative elements present in it in linear time.

For example,

Input:

[ -7 -3 -1  3  5  ]
[ -3 -2  2  4  6  ]
[ -1  1  3  5  8  ]
[  3  4  7  8  9  ]

Output:

The total number of negative elements present is 6.

Practice this problem

We can do a binary search to find the last occurrence of a negative number or the first occurrence of a positive number for each row. The complexity of this solution will be O(M × log(N)), which is not linear as per problem time constraints.

The idea is to take advantage of the fact that the matrix is row-wise and column-wise sorted. Start from the matrix’s top-rightmost cell and do the following until the matrix boundary is reached:

• If the current element is negative, increment the negative count and move to the next row.
• If the current element is positive, move to the left cell.

The algorithm can be implemented as follows in C++, Java, and Python:

## C++

Output:

The total number of negative elements present is 6

## Java

Output:

The total number of negative elements present is 6

## Python

Output:

The total number of negative elements present is 6

The time complexity of the proposed solution is O(M + N) for an `M × N` matrix and doesn’t require any extra space.

Exercise: Count zeros in a row-wise and column-wise sorted matrix.