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