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++


Download  Run Code

Output:

The total number of negative elements present is 6

Java


Download  Run Code

Output:

The total number of negative elements present is 6

Python


Download  Run Code

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.