Count negative elements present in sorted matrix in linear time

Given a M x N matrix which is row wise and column wise sorted, count 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:

Total number of negative elements present are 6

 

 
We can do binary search to find last occurrence of negative number or first occurrence of a positive number for each row. The complexity of this solution will be O(MlogN) 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. We start from the top-rightmost cell of the matrix and do the following till matrix boundary is reached –

– if current element is negative, we increment the negative count and move to the next row.
– if current element is positive, we move to the left cell.

 

C++

Download   Run Code

Output:

Total number of negative elements present are 6

Java

Download   Run Code

Output:

Total number of negative elements present are 6

 
Time complexity of above solution is O(M + N).
Auxiliary space used by the program is O(1).

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of