@ Matrix[N][M]

An integer matrix N*M has all its rows and columns sorted.Given an integer k, find whether it is present in the matrix or not. (efficient algorithm expected)

Are you looking for a constant time algorithm?

If we treat it as a single dimension array, we would anyways have a O(log(m*n)) solution in binary search.

To refine it more. you can take the last elements of rows and search the first row which has the row-ending number just greater than the number that you are searching for (use binary search). Then you can do a binary search on that row for that number. This method would be a O(log(m) + log(n)) method.

But as I said, this is a trivial solution. Are you looking for a constant time algorithm. If giving out the complexity gives a hint to the solution, then please just suggest that a smarter algorithm exists.

do u think ur algo will work for the following input:

1 2 3 4

5 6 8 9

7 10 11 12

The no. to search in the matrix is 7.

I got your question wrong ... now I see what you are asking for

I wish I could draw here or attach a file.

But the basic idea is simply move along the diagonal from [0][0] to [min(m-1,n-1)][min(m-1,n-1)]. After this if m>n move down the rows with the last element of the rows starting from [min(m-1,n-1)][n-1] to [m-1][n-1] Else if you n>m move along the last elements of each column starting from [m-1][[min(m-1,n-1)] to [m-1][n-1].

Observation{ along the defined diagonal, let A[i][j] and A[k][l] be 2 consecutive elements such that A[i][j]<key<A[k][l], then key can not be part of upper-left-rectangular-sub-matrix A[0][0] <-> A[i][j] as all these elements are smaller than A[i][j] which is < k. Also, key can't be in the lower-right-rectangular-sub-matrix from A[k][l] <-> A[m-1][n-1]. as all of these are greater than A[k][l] and key < A[k][l]. key can however lie in the lower-left-rectangular-sub-matrix A[k][0] <-> A[m][l-1] or upper-right-rectangular-sub-matrix A[0][l] <-> A[k-1][n-1].

With the above observation, we solve this problem recursively. We look in the body diagonal, if we find that key > last element of diagonal, then we return false. If we find the key, we return true. Else we find the first element which is bigger than key. We now recursively call search in matrices upper-right-rectangular-sub-matrix and lower-left-rectangular-sub-matrix. If any of these sub matrices return true, we return true. Else if both of these matrices are trivially small or both return false, then the answer returned is false.

Let me know if there is something smarter. The complexity of this algorithm is O(log(max(m,n))

first of all the complexity won't be log(max(m,n))....
to make the complexity calculation easier taking your algorithm into account.. lets say the matrix is of size N * N where N = pow(2,k)..

In this case the complexity would be, summation(i=0 to n) on (2^i)(k-i)... which is nothing but (2N - logN -2) i.e. O(2N)..
Now we can say that if the matrix was of size M*N, then the complexity would be
O(M+N)...

Though your solution is correct but there is a better way to do it...( it doesn't require recursion )....

apologies!

will have a shot at it later

hey is there anybody who would like to take a different approach to solve this problem....

Please don't give out the solution. It is an interesting problem to solve

sure

As you know that the matrix is sorted row-wise as well as column-wise. If any element of the matrix is picked at random then the following is true,
- all the elements to the left of the current element(in the same row) are <= the current element.
- all the elements to the right of the current element(in the same row) are >= the current element.
- all the elements above the current element(in the same column) are <= the current element.
- all the elements below the current element(in the same column) are >= the current element.

Say,
Matrix is A[M,N]
Search element is K

Lets start from the top-right corner of the matrix..
currElement = A[1,N]
found = FALSE;
while (!found && (elements left to be searched))
{
if (currElement < K)
{
discard the current column.
go to the element left to current element in the same row. ( currElement = A[1,N-1] )
continue;
}
else if (currElement > K)
{
discard the current row.
go to the element below the current element in the same column. ( currElement = A[2,N] )
continue;
}
else
{
found = TRUE;
break;
}
}

Complexity = O(M + N) , the max time taken by the above algo would be (M + N) runs of the while loop.

/* --- Working code --- */

int A[M][N]; // given matrix..

int i = 0; // 'i' represents the row..
int j = N-1; // 'j' represents the column..
bool found = FALSE;
int K ; // search element
int currElement;

while (!found && i!=M && j!=-1)
{
currElement = A[i][j];
if (currElement < K) { --j; }
else if (currElement > K) { ++i; }
else { found = TRUE; }
}