@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.