Report all occurrences of an element in row wise and column wise sorted matrix in linear time

Given a M x N matrix which is row wise and column wise sorted (with all strictly increasing elements in any row or column), report all occurrences of a given element in it in linear time.


For example,


Input:

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

Output:

Element 3 found at position (0, 3)
Element 3 found at position (2, 2)
Element 3 found at position (3, 0)

 


 
We can do binary search to find index of first occurrence and index of last occurrence of given key 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 –

  1. If current element is less than the key, we increment row index (move to the next row)
     
  2. If current element is more than the key, we decrement column index (move to the previous column)
     
  3. If current element is equal to the key, we print the current location and increment row index & decrement column index to find next location of the key in given matrix. This will work as matrix contains all strictly increasing elements in any row or column.

 
C++ implementation –
 

Download   Run Code

Output:

Element 3 found at position (0, 3)
Element 3 found at position (2, 2)
Element 3 found at position (3, 0)

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

 
We recommend to visit below links to check more efficient solutions to solve this problem –

 
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