CareerCup

For any given mXn matrix M[0][0] and M[m][n] gives the range of the matrix

1. Divide the MATRIX into 4 submatrices.
2. For each of the 4 matrices check the range(s) and eliminate the matrices. At least one of the 4 submatrices is eliminated in this step.
3. Repeat recursively untill, submatrix consists of one element.


Recursive relation : T(n) = 3T(n/4) + O(1)
Complexity : less than O(n)

if Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order....

This algorithm works by elimination. Every move to the left (--col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.


boolean FindElem(int[][] mat, int elem, int M, int N) {
int row = 0;
int col = N-1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
return false;
}

As told by sanjay, suppose we are looking for 11,
based on diagonal search we find that 11 lies in between 8 and 12, so 11 can lie in either
[3 11
4 14]
or
[6 7
9 10]
follow same procedure for these blocks and continue.
complexity,
N + N/2 + N/2^2 .. = 0(log2(N))

Bhagwan Shri Ramchandra ki jai....
Now see the solution....
Let matrix M[1,1],M[1,2],....M[1,N]
...
...
M[N,1],M[N,2],....M[N,N]

Short Algo-
1. Do binary search on the 1st column to locate the row where x could be - O(lgN)
2. Do binary search in the found row to locate x. - O(lgN)

Detailed algo -
Step 1. // Search 1st column to get the row_num where x might belong
1.first=1, last=N
2.while(first<last) {
2.1 mid=floor((first+last)/2);
2.2 if(M[mid,1]<x), first=mid+1; flag=1
2.3 else if(M[mid,1]>x), last=mid-1; flag=2
2.4 else return(mid) //mid as row_num to be checked for x
}
3. if(flag==1) return(first-1) //first-1 as row_num to be checked for x
4. if(flag==2) return(last+1) //last+1 as row_num to be checked for x


Step 2. //Search row_no row for element x
1. first=1, last=N;
2. while(first<last) {
2.1 mid=floor((first+last)/2);
2.2 if(a[mid]<x), first=mid+1;
2.3 else if(a[mid]>x), last=mid-1;
2.4 else return(mid)) //mid as column number containing x
}
3. return(-1) // x not present

row_num,col_num = position of x

Jay bolo Shri Ram ji ki....
Ram Lakshamana Jaanki, Jay bolo Hanuman ki....

I've found a proof that this problem is not solvable with anything better than O(n) in the worst case. Consider a special case of matrix M:

1 1 1 ... 1 (2 or 3)
1 1 ... (2 or 3) 4
1 .... (2 or 3) 4 4
.................................
1 (2 or 3) 4 4 ... 4 4
(2 or 3) 4 4 4 ... 4 4

If you are required to find, say, value "3", your task will be not easier than finding said "3" in arbitrary (not necessarily sorted) array of 2-s and 3-s. Proof: consider array of 2-s and 3-s, place it on that diagonal of matrix M, if you can find 3 faster than O(n), than you can find it in the given array too, which is apparently not possible.

Can you write your solution?

This is exactly the same as binary search..

This is a binary search in 2D version.

Better then this... use the Diagonal as a shorted array... and use modified version of binary search...

1   5  6  7
2   8  9 10
3  11 12 13
4  14 15 16

the diagonal is 1 8 12 16.. use the binary search on this to find out the nearest element of the number and then check the adjustment element of nearest element to find out the number.

if the matrix is n by n. what is considered as the the input size? n or n square?

what about using three binary search.
bool Search(int matrix[][M_SIZE], int k)
{
int start = 0, end = M_SIZE-1;
int middle;
while (start <= end)
{
middle = (start+end)/2;
if (matrix[middle][middle] == k)
return true;
else if (matrix[middle][middle] > k)
end = middle-1;
else
start = middle+1;
}
if (matrix[middle][middle] < k)
return false;
int line = middle;
// dprint(line);

start = 0, end = line;
while (start <= end)
{
middle = (start+end)/2;
if (matrix[line][middle] == k)
return true;
else if (matrix[line][middle] > k)
end = middle-1;
else
start = middle+1;
}

start = 0, end = line;
while (start <= end)
{
middle = (start+end)/2;
if (matrix[middle][line] == k)
return true;
else if (matrix[middle][line] > k)
end = middle-1;
else
start = middle+1;
}

return false;
}

kamino, kuch seekho

I may be wrong here. But I don't think a O(logn) solution exsists.

Here is a O(logn) solution
1. Start with [0][0] Location and check max value of the Row and Column i.e. [0][ColMax] and [rowMax][0]
2. If the value is outside the range Move diagonally down e.g. Matrix[1][1] and Goto Step 1
If reached last diagnol then return with value not found
3. Search within the Row and Column

Moving along the diagonol is O(log(n)) . Then searching element in the row or column is O(logn) + O(log n) = O(log n). So overall it is O(log n ) algorithm where n is size of the col/row

1. Using binary search find the row which might contain the number given. Gives O(log(n)) complexity.
2. Do same to find the column in the row found

If the matrix is sorted both on its columns and rows (and assuming the sort order is ascending for both columns and rows), you can process the matrix as a simple linear array of sorted values and use a simple binary (O(logN)) search to find the sought value or confirm that the values is missing from the matrix.