Thursday, September 10, 2015

Next Greater Element

Problem Statement:-
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

Solution in JAVA int time complexity O(n) 
import java.io.*;
import java.util.*;
class nextGreater
{
    public static void nextGreat( int a[], int len)
    {
        int element, next;
        Stack mystack = new Stack();
        for(int i=0; i<len; i++)
        {   
            next = a[i];
            while(!mystack.empty())
            {
                element=(int)mystack.pop();
                if(element > next)
                {
                    //push back the element 
                    mystack.push(element);
                    break;
                }
                else
                {
                    System.out.println( element +"-------->"+next);
                }
            }
            mystack.push(a[i]);
        }
        while(!mystack.empty())
        {
            element = (int)mystack.pop();
            System.out.println( element +"-------->"+"-1");
        }
        return;
    }
    public static void main(String []args)
    {
        int a[] = {1,2,23,3,4,205,25,1,2,100,2,3,4,200,105};
        nextGreat(a,a.length);
     }
}

Thursday, September 3, 2015

Minimum Initial Points to Reach Destination


Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0).


Constraints :
  • From a cell (i, j) we can move to (i+1, j) or (i, j+1).
  • We cannot move from (i, j) if your overall points at (i, j) is <= 0.
  • We have to reach at (n-1, m-1) with minimum positive points i.e., > 0
Example

Input: points[m][n] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };
Output: 7
Explanation: 
7 is the minimum value to reach destination with 
positive throughout the path. Below is the path.

(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)

We start from (0, 0) with 7, we reach(0, 1) 
with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)
with and finally we have 1 point (we needed 
greater than 0 points at the end). 

pasting the code below, please let me know if you found any bug in it.
import java.io.*;

class minInitialDP
{
    public static int max(int x, int y)
    {
        return (x>y?x:y);
    }

    public static int min(int x, int y)
    {
        return (x<y?x:y);
    }

    public static void main(String []args)
    {
        int points[][] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };

        int DP [][] = new int[3][3];

        // main code goes here 

        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                if (i==0 && j==0)
                {
                    DP[i][j] = 0;
                    continue;
                }

                if( i==0 )
                {
                    if(points[i][j-1] < 0)
                    {
                        DP[i][j] = -points[i][j-1]+DP[i][j-1]+1;       
                    }
                    else
                    {
                        DP[i][j] = DP[i][j-1];
                    }
                    continue;
                }

                if(j==0)
                {
                    if(points[i-1][j] < 0)
                        DP[i][j] = -points[i-1][j]+DP[i-1][j]+1;
                    else
                        DP[i][j] = DP[i-1][j];
                    continue;
                }

                int pi, pj;

                if(points[i][j-1] < 0)
                    pi = -points[i][j-1]+DP[i][j-1]+1;
                else
                    pi =  DP[i][j-1];

                if(points[i-1][j] < 0)
                    pj = -points[i-1][j]+DP[i-1][j]+1;
                else
                    pj = DP[i-1][j];

                DP[i][j] = min(pi, pj);
            }
        }

        for(int i=0; i<3; i++)
        {
            for(int j =0; j<3; j++)
                 System.out.print(DP[i][j] + " ");
            System.out.println("\n");
        }
    }

}

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