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

     }

}