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

Download   Run Code

Output:

Total number of negative elements present are 5

 
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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz