CareerCup

Perform Binary search in each and every row. I think this is optimal with complexity O(n log n)

1-check the first element of the each row if first element is greater than the item to be searched ignore that row.
2-check the last element of each row if it is less than item to be searched ignore this row also.
do 1 and\or 2 for every row and after that apply the binary search on remaining row.

@Maxximus, @Kuldeep
Your estimate for time complexity is wrong. Its still O(nlogn). Filtering rows on basis of range does not guarantee that the number of valid rows will be very small compared to n. You can easily imagine a matrix for which n=1000000 and number of invalid rows = 100. In these cases, even after filtering the number of rows is O(n) and for each row a binary search means O(logn) time for that row. Thus, it still comes out O(nlogn).

Hmm.... anyone knows better than O (n log n) ??
O(n log n) is trivial .....

we can skip some rows checking if the number lies in the range for the row.
but worst case nlogn

Also, if the matrix is like { 1 4 7
2 5 8
3 6 9}
and if we want to search for 5, we can't eliminate any rows by looking at the range. We are compelled to do the binary search on every row

I think it should be O(nlogn)...in the worst case ..and yaa we can check whether element is present between the range of first element of row and last element of row and accordindgly we can call binary search

The matrix is sorted row-wise also means you consider the elements in each column, they are also sorted top down. So, we can first perform a binary search on say the first column, reach a particular row and then perform another binary search on the row to get to the required element.
For a MxN matrix, this solves the problem in O(log M) + O (log N)
You just need to search the required row !!

Guys. I dont know who is using my name and posting rubbish comments

Create a one dimentional sorted array outofit which can be done in o(n) time
Now searching for an element in this wll take o(logn). This will give us o(n) + o(logn) time i.e. o(n) time. Please let me know if i am wrong here

The program logic is very easy. It has been made little tricky. :-)

find the row by checking the range and then do a binary search on the row

find the row by checking the range and then do a binary search on the row

I think O(nlogn) is correct

Maintaining a HashMap<RowNo,Lowest Element> would enable O(n - no of elements in a row) search

Just as Kuldeep mentioned, check the range and then do a binary search on the particular row. Checking the range takes O(n) as we need to scan N rows and this will dominate the algorithm complexity. So it does take only O(n) instead of O(nlogn)

We need to use matrix properties in this ques. start from any element in the matrix and compare with elements which is around that element, then move your pointer to the element which is more close to it then again repeat the process until you find the element.

Using magnifying glass! LOL!

You f***kng people!!!!!!!!! I am a LOLER LOL LOL LOL!!!! CLAP CLAP CLAP