Last Updated: 31 Aug, 2020

Next Greater Element

Easy

Asked in companies

Solve now

Problem statement

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.

Input Format:

The first line of input contains an integer 'n' representing the size of the array.

The second line of input contains 'n' single space-separated integers representing the elements of the array.

Output Format :

The only line of output contains 'n' single space-separated integers representing the Next Greater Element for each element.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

For every element in the array, we will run a loop on its right side. As soon as we find an element on its right side which is greater than it, we will break the loop, assign it as the NGE of this element, move forward, and do the same for the next element.

Solve now

02 Approach

We will use a Stack to keep track of the next greater element and pop as soon as we find an element greater than it.

Here is the complete algorithm:

Create a new array 'ans[ ]' of the same size as the input array to store the Next Greater Elements.
Declare a stack that will have Next Greater Element as its top element.
Traverse the array in reverse order and for every element at i-th index:
- Pop the stack until the current element is greater than the top element of the stack.
- Update ans[i] with the top element of the stack or -1 if the stack is empty.
- Push the current element onto the stack.
Return ans.

Solve now