Saturday, August 22, 2015

Find length of the longest consecutive path from a given starting character

Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. It is allowed to move in all 8 directions from a cell.

example:

for mat[][]={{a,c,d},
                     {h,b,e},
                     {i,g,f}} 
and input character 'e' o/p will be 5

At first this problem is looking easy (Indeed this is) by simply finding the next character via doing a 8 way recursion, this is doable this way but we can do it more efficiently by using dynamic programing, there can be some subproblem while we are searching for a path so we will store that paths in our dp matrix and will use it in between.

simple solution in java 

class SearchPath
{
    public static final int R=3;
    public static final int C=3;

    // matrix for tracking purpose 
    public static boolean [][] visited;
    
    //input matrix
    public static char [][] mat ={ {'a','c','d'},{ 'h','b','a'},{ 'i','g','f'}};
    
    // just storing all 8 position for iterative recurs 
    public static int [] x = {1,0,1,1,-1,-1,0,-1};
    public static int [] y = {0,1,1,-1,1,-1,-1,0};
    
    //dp storage
    public static int [][]dp;
    
    public static int max(int a, int b)
    {
        return(a>b?a:b);
    } 

    //will check if and i,j pair in matrix valid or not
    public static boolean isValid(int i, int j)
    {
        if(i<0 || j<0 || i>=R || j >=C)
            return false;
        else
            return true;
    }
    
    public static int getpath_util(char m, int r, int c)
    {
        if(!isValid(r,c) || visited[r][c] ||  m+1 != mat[r][c])
            return 0;
        if(dp[r][c]!= -1)
        {
            return dp[r][c];
        }
        
        // make this visited so in subsequent call it will not be taken into account
        
        visited[r][c] = true;
        int ans=0;
        for(int k=0; k<8; k++)
        {
            ans= max(ans, 1+getpath_util(mat[r][c], x[k]+r, y[k]+c));
        }  
        
        // unset this
        visited [r][c] = false;
        
        return dp[r][c] = ans;
        
    }
    public static void getpath(char m)
    {
        int ans=0;
        for(int i=0; i<R; i++)
        {
            for(int k=0; k<C;k++)
            {
                if(mat[i][k] == m)
                {
                    for(int j=0; j<8; j++)
                    {   
                        ans = max(ans, 1+getpath_util(m, i+x[j], k+y[j]));
                    }       
                }
            }
        }   
        System.out.println(ans);
    }
    public static void main(String[]args)
    { 
        visited  = new boolean[R][C];
        dp = new int [R][C];
        for(int i=0; i<R;i++)
            for(int k=0; k<C; k++)
                dp[i][k]=-1;
        for(int i=0; i<R;i++)
            for(int k=0; k<C; k++)
                visited[i][k]=false;
        getpath('a');
        getpath('e');
        getpath('b');
        getpath('f'); 
    }

}


Source:- gfg

Thursday, August 20, 2015

Merge two sorted linked list (Recursive Approach)


Merge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code

Node *Merge(Node * head1, Node *head2)
{
        // Base conditions

       if(! head1 || !head2)
       {
              if(!head1)
                   return head2;
              else
                   return head1;
     
        }
        else
        {

                 if(Node1.data <= Node2.data)
                 {

                        Node1.next = Merge(Node1.next, Node2)
                        return Node1;

                 }
                 else
                 {
       
                       Node2.next= Merge(Node1, Node2.next);
                       return Node2;
                 }
        }

}

Tuesday, August 18, 2015

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped
Solution:
Simple approach is to find rightmax and leftmax of every element and determine the excess water, it can be calculated by formula:
trap_water_on_current_bar = min(leftmax, rightmax) - current_value

Implementation:
int findWater(int arr[], int n)
{
    int *max_left = new int[n] ;
    int *max_right = new int[n];
    int water = 0;
    // Fill left array
    left[0] = arr[0];
    for (int i = 1; i < n; i++)
       left[i] = max(left[i-1], arr[i]);
    // Fill right array
    right[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--)
       right[i] = max(right[i+1], arr[i]);
    // Calculate the accumulated water element by element
    // consider the amount of water on i'th bar, the
    // amount of water accumulated on this particular
    // bar will be equal to min(left[i], right[i]) - arr[i] .
    for (int i = 0; i < n; i++)
       water += min(left[i],right[i]) - arr[i];
    return water;
}

Source:- LeetCode, GeeksForGeeks