@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a O(m*n)
matrix in O(n) but answer of this question is given already in the
question that " all row & column are sorted so why O(n) solution
exist " it really matters & play very important role if one will
think out of box....well i think inside the box.not outside...lol
here we go for O(n) Clean ,Elegant ,Simple & Best Solution as i
think for this problem
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)//done
{
return true;
}
else if (mat[row][col] > elem) //obvious as all call are sorted
because all value in col[j] < col[j+1] given test below program for
searching element 2
{
col--;
}
else // its all same as all row are sorted so if element not found
in a[i][] then got a[i+1][] row because all all value in row[i] <
row[i+1] its given
{ //
test below program for searching element 9
row++;
}
}
return false;
}
Working Code https://ideone.com/64HJg
If u found for any counter test case its failing then plz let me know
still f any has doubt i will try to explain my best
Thanks & Regards
Shashank Mani>> "the Best way to escape from The Problem is Solve It"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
