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");
        }
    }

}