JIGYASA

An online placement forum.


You are not connected. Please login or register

@ Matrix[N][M]

Go down  Message [Page 1 of 1]

1 @ Matrix[N][M] on Sun Mar 07, 2010 6:30 am

Lucifer


Admin
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)

View user profile http://jigyasa.forumn.org

2 trying to understand your question better on Sat Mar 13, 2010 2:23 am

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.

View user profile

3 @indranil on Sat Mar 13, 2010 11:11 pm

Lucifer


Admin
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.

View user profile http://jigyasa.forumn.org

4 Re: @ Matrix[N][M] on Tue Mar 23, 2010 6:48 am

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

View user profile

5 Re: @ Matrix[N][M] on Tue Mar 23, 2010 9:49 am

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

View user profile

6 @indranil on Wed Mar 24, 2010 2:35 am

Lucifer


Admin
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 Smile )....

View user profile http://jigyasa.forumn.org

7 My bad! on Wed Mar 24, 2010 2:54 am

apologies!

will have a shot at it later Razz

View user profile

8 @everyone on Wed Apr 07, 2010 4:13 am

Lucifer


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

View user profile http://jigyasa.forumn.org

9 @Lucifer on Wed Apr 07, 2010 4:16 am

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

View user profile

10 @indranil on Wed Apr 07, 2010 4:28 am

Lucifer


Admin
sure Smile

View user profile http://jigyasa.forumn.org

11 Re: @ Matrix[N][M] on Tue Sep 21, 2010 7:05 am

Lucifer


Admin
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; }
}

View user profile http://jigyasa.forumn.org

Sponsored content


Back to top  Message [Page 1 of 1]

Permissions in this forum:
You cannot reply to topics in this forum