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 –

- If current element is less than the key, we increment row index (move to the next row)

- If current element is more than the key, we decrement column index (move to the previous column)

- 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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> using namespace std; // M x N matrix #define M 4 #define N 5 int findElement(int mat[][N], int key) { // start from (0, N-1) i.e. top-rightmost cell of matrix int i = 0, j = N - 1; // run till matrix boundary is reached while (i <= M - 1 && j >= 0) { // if curr element is less than the key, increment row index if (mat[i][j] < key) i++; // if curr element is more than the key, decrement col index else if (mat[i][j] > key) j--; else // curr element is equal to the key { cout << "Element " << key << " found at position (" << i << ", " << j << ")" << endl; i++; j--; } } } // main function int main() { int mat[M][N] = { { -4, -3, -1, 3, 5 }, { -3, -2, 2, 4, 6 }, { -1, 1, 3, 5, 8 }, { 3, 4, 7, 8, 9 } }; findElement(mat, 3); return 0; } |

`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).

Below links contains more efficient solutions for 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