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 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.
We use the Stack based approach to find the next greater element.
Fill the next greater element array to -1
Loop over the elements and perform the below operations i. Push the index to stack if stack top is greater than the current element ii. Loop and Pop until the stack top is less than the current element, and update the popped index with the current element