Next Greater Element

Next Greater Element

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.

Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) 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

d) For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.

  Element        NGE

   13      -->    -1

   7       -->     12

   6       -->     12

   12     -->     -1

Java Solution using Stacks :

package nextGreaterElement;
import java.util.Stack;
public class NGE // next greater element
{
 public static void main(String[] args) 
 {
  int A[]={7,8,9,4,5,6,1,2,3};
  Stack<Integer> S=new Stack<Integer>();
  S.push(new Integer(A[0]));
  for(int i=1;i<A.length;i++)
  {
   int current=A[i];
   while(true)
   {
    if(S.isEmpty())
    {
     S.push(new Integer(current));
     break;
    }
    int element=S.pop().intValue();
    if(element>current)
    {
     S.push(new Integer(element));
     S.push(new Integer(current));
     break;
    }
    System.out.println(element+" -> "+current);
   }
  }
  while(!S.isEmpty())
   System.out.println(S.pop()+" -> "+"-1");
 }
}

Time Complexity : O(n)
Note that when you use two loops to iterate through the array to find the next greater element your time complexity will be O(n*n), but by using the above mentioned method of stacks, we can reduce the time complexity to O(n).