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).
       

Given only parent array find height of a genric tree | java implementation

Hello friends,

I recently came across an interesting question on Tree. The problem statement is as below:

Suppose a generic tree has N nodes and nodes are named using the numbers between inclusive range 0 to N-1. An array of Integers, named 'parent' , is given, such that  'parent[i]' represents name of the parent node for node-i. For the root value stored in 'parent' array is -1. Find the height of the Tree.

Friends Points to note are :

1. Tree is generic and not necessary a Binary tree.
2. Only information we have is of Parents of each node.
3. Root is not necessarily at position 0, as it is not mentioned in the problem statement.

Lets see this with a diagram.



Lets see the parent array for this tree

int[] parent = {6,6,6,-1,3,0,3};

Friends to solve this we will first compute the depth of each node and memorize it. Using above information, depth of any node can be simply calculated by adding 1 to the depth of its parent. The node at maximum depth will be the height of the tree.

Lets see the implementation in Java for solving this problem

 

package generictree;
/**
 * 
 * @author Krishna.k
 * 
 *         Suppose a generic tree has N nodes and nodes are named using the
 *         numbers between inclusive range 0 to N-1. An array of Integers, named
 *         'parent' , is given, such that 'parent[i]' represents name of the
 *         parent node for node-i. For the root value stored in 'parent' array
 *         is -1. Find the height of the Tree.
 *
 */
public class FindHeightGivenParentArray {
    public static void main(String[] args) {
        int[] parent = { 6, 6, 6, -1, 3, 0, 3 };
        int N = parent.length;
        System.out.println("height of tree is " + getHeightOfTree(parent, N));
    }

    public static int getHeightOfTree(int[] parent, int N) {
        int[] depths = new int[N];
        int maxDepth = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (depths[i] == 0) {
                int depthOfIthNode = findDepthOfIthNode(parent, depths, i);
                if (maxDepth < depthOfIthNode) {
                    maxDepth = depthOfIthNode;
                }
            }
        }
        return maxDepth;
    }

    public static int findDepthOfIthNode(int[] parent, int[] depths, int i) {
        if (depths[i] != 0) {
            return depths[i];
        }
        if (parent[i] == -1) {
            depths[i] = 1;
            return depths[i];
        }
        depths[i] = findDepthOfIthNode(parent, depths, parent[i]) + 1;
        return depths[i];
    }
}

The Output for the above program on console is :
height of tree is 4