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

No comments:

Post a Comment