Next Greater Element (NGE)

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.

Facts about NGE:

• For any array, rightmost element always has next greater element as -1.
• For an array which is sorted in decreasing order, all elements have next greater element as -1.
• For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.

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

Algorithm:

• Create Stack to hold larger values
• Iterate given array from start to end
  • If stack not empty and stack.top < array[i] then,
    • Print "NSF of stack.pop is array[i]"
  • stack.push (array[i])
• Iterate stack till not empty
  • Print "NSF of stack.pop is -1 "

Latest Source Code:
Github: NextGreaterElement.java

Output:

4 --> 5
2 --> 25
5 --> 25
25 --> -1


250 --> -1
300 --> -1
350 --> -1
400 --> -1