In last post I talked about finding 1-D array peak.

A peak in a 2-D array is an element which has left, right, top and bottom elements lower than it. A simple approach will be to extend the 1-D array approach. Treat each row (or column) as 1-D array, and apply 1-D peak finding algorithm, which we know takes lgN operations. Once we find that we will check if this is 2-D peak as well (a 2-D peak is 1-D peak by default, but not vice versa). If yes, we are good, else continue with next row.

In case we have a N*N 2-D array, above algorithm gives me a time complexity of N*lgN.

Lets improve the above complexity by introducing divide and conquer approach.

1. Divide the matrix (2-D array) into 4 equal parts, divided on mid row and mid column.
2. Find the local peak (highest element) in row and column.
3 a. If local peak is found in horizontal column (we know left and right are small), check if top and bottom are small, if yes current element is 2-D peak, if no, choose the sub matrix which has higher (top or bottom) number than current element.
3 b. If local peak is found in vertical row (we know top and bottom are small), check if right and left are small, if yes current element is 2-D peak, if no, choose the sub matrix which has higher (left or right) number than current element.
4. After 3, we have got a matric of N/4*N/4 size of inital matrix. Repeat from 1 with new matrix.

1 2 3 4 5
1 9 7 5 3
2 3 6 5 3
3 2 4 8 1
1 9 2 3 7

7 is found as local maximum, but 9 on left is larger so we move ahead

Step 2
1 2 3
1 9 7
2 3 6

Repeating steps above give us 2-D peak

Complexity
Step 1: Check N+N elements to find the maximum= T(N/2)+ CN
Step 2: Check N/2+N/2 elements= T(N/4)+C(N/2)+CN
= T(N/8)+C(N/4)+C(N/2)+CN
…
=T(1)+CN(1+1/2+1/4+1/8+….1/N)
we get a geometric series which tends to 1.
Hence overall complexity O(N)

A peak in a 1-D array is simply an element which has left and right elements smaller than it.

1, 3, 4 ,6 ,9, 11, 14, 12, 7, 3, 2

14, clearly is peak here.

A straight forward algorithm would be to parse the array from left to right and keep checking if a[index]>=a[index+1] and a[index]>a[index-1], we have found a peak.

The above algorithm gives me a complexity of O(N).

An improvement over above approach to user divide and conquer approach, like we do in binary search.

1. Go to mid of the array Arr[N/2]
2. Check if it is peak (left and right are smaller)
3. check if left element is larger than mid element, if yes, NewArr= Arr[0..N/2-1]
4. else NewArr=Arr[N/2+1..N]
5. Repeat from 1 with NewArr

Complexity

T(N)=T(N/2)+C //at every step we will divide the array into 2, C is constant time taken in the opertaion
=T(N/4)+C+C
=T(N/8)+C+C+C
=T(N/2^k)+CK
… total number of steps is lg(N)
=T(1)+C*lg(N)

or O(lgN) complexity.

Sometime back I talked about Graph data structure.

One of the important usage of graph is to find the shortest path from one node to another, for example in travelling salesman problem.

One important algorithm to find shortest path for between two nodes in graph is Dijkstra’s algo.

Here is how

Image source wikipedia

1. Mark All node distance as infinity (to mark that node has not been traversed yet)
2. Start from source node, add all other nodes to a set contaning unvisited node
3. Traverse all neighboring nodes from current node N and calculate distance from previous node by adding distance[N] + distance from N to this node (edge weight)
4. When all neighbors are calculated, mark current node as visited.
5. If we have visited the destination node, exit with the distance till destination node.
5. Pull next node from set.
6. Goto 3.

Read more here

Finding longest repeating sub-sequence or substring among a string is classic CS problem. Here is one simple solution where we use approach of finding all the substrings from beginning and sort the resulting array. In sorted array we will find longest common repeating sub-sequence.

Input: banana

Output: ana

//method to return longest subsequence
public static String findLongestSubsequence(String str)
{
String sub=””;

String arr[]=new String[str.length()];
//Firstly lets find all the substrings
for(int i=0;i<str.length();i++)
{
arr[i]=str.substring(i);
}

//as we have the list of all substrings, sort them
Arrays.sort(arr);

//compare strings with next string and find the maximum length common substring
for(int i=0;i<arr.length-1;i++)
{
//compare arr[i], arr[i+1]
int len=(arr[i].length()<arr[i+1].length())?arr[i].length():arr[i+1].length();
String temp=””;

for(int j=0;j<len;j++) { //compare two strings till a point where they are equal if(arr[i].charAt(j)==arr[i+1].charAt(j)) temp=arr[i].substring(0,j+1); else break; } sub=(temp.length()>sub.length())?temp:sub;
}

return sub;
}

There are other ways to find longest repeating sub-sequence. One  important way is to create a m*n matrix with a value showing length of subsequence till that point

b a n a n a
b   0 0 0 0 0 0
a   0 0 0 1 1 1
n   0 0 0 1 2 2
a   0 1 1 1 2 3
n   0 1 2 2 2 3
a   0 1 2 3 3 3

Another sophisticated way is to create a suffix tree. Read more here –http://en.wikipedia.org/wiki/Suffix_tree

I had discussed Breadth first and Depth First traversal algorithms sometime back.

There are 3 important traversing algorithms for tress. http://en.wikipedia.org/wiki/Tree_traversal

InOrder
-Travel Left, Travel Root, Travel Right.

PreOrder
-Root, Left, Right

PostOrder
-Left, Right, Root

Here is recursive implemenation
public void inOrder(Node root)
{
if(root.left!=null)
inOrder(root.left);
System.out.println(root.number);
if(root.right!=null)
inOrder(root.right);
}

public void preOrder(Node root)
{

public void postOrder(Node root)
{
if(root.left!=null)
postOrder(root.left);
if(root.right!=null)
postOrder(root.right);
System.out.println(root.number);
}