Searching in a Row-wise and Column-wise sorted 2 d matrix.

Dear Friends,

I am here with you with a tricky algorithmic question. It is based on searching an element in 2 D matrix which is sorted row wise and column wise. Please find the problem details below.

A matrix with R rows and C columns such that it is sorted row wise and column wise. For any element, 'e', in the matrix, positioned at 'r' and 'c', as compared to e we have:

1. All elements towards its LEFT are SMALLER.
2. All elements towards its RIGHT are GREATER.
3. All elements above it are SMALLER.
4. All elements below it are GREATER.

We have been given a number 'X' which we have to find if it exists in the matrix or not.

The top-most left element has the position of (0,0) and bottom-most right element is positioned at (R-1,C-1).





Above is an example of such matrix. Here R = 4 [ as rows are 4 ] , C = 5 [ as columns are 5 ].

Suppose we need to find 35, so for this case our X = 35.

1. Basic approach is traversing all the elements in the matrix this approach has time complexity of O(R*C).
2. Another approach is to do binary search in each row. This will have time complexity of O(C*logR).
3. Another approach is  to start from topmost right element. We know that as compared to the topmost right element, all the elements to its left are smaller and all the elements below it are greater. 
• In a loop and starting with topmost right element.
• if X is equal to element, print "Element found" and return.
• if  X is smaller than element, move LEFT, i.e. decrease column by 1.
• if X is greater than element, move DOWN,  i.e. increase row by 1.

• continue looping until column >= 0 and row < R.
• If the loop completes, print "Element is not found".

Friends refer to the Java program implementing the 3rd approach.

package sortedmatrix;

public class FindElementInSortedMatrix {
    public static void main(String[] args) {
        int[][] sortedMatrix = 
            { 
                { 1, 5, 8, 9, 20 }, 
                { 4, 7, 25, 30, 32 }, 
                { 5, 20, 33, 35, 40 },
                { 10, 24, 38, 45, 50 } 
            };
        int R = sortedMatrix.length;
        int C = sortedMatrix[0].length; // assuming all rows have same number of
                                        // columns
        int X = 35;
        findPositionOfX(R, C, sortedMatrix, X);
    }

    private static void findPositionOfX(int R, int C, int[][] sortedMatrix, int X) {
        int r = 0, c = C - 1;
        // directions possible are left and down.
        // left => decrement in columns, 0 will be the limit
        // down => increment in row, R-1 will be the limit
        while (r <= R - 1 && c >= 0) {
            if (sortedMatrix[r][c] == X) {
                // success, elemt has been found.
                System.out.println("Sucess!!, elecment found at r =" + r + " c=" + c);
                return;
            }
            if (X < sortedMatrix[r][c]) {
                // move left
                c = c - 1;
            } else {
                // move down
                r = r + 1;
            }
        }
        System.out.println("Element is not present in the matrix");
    }
}

Maximum hops for columns can be starting from right move all steps towards left till column becomes 0 and maximum hops for rows can be starting from top to move all steps below until row becomes R-1. So time complexity of this approach is O(R + C).