Last Updated: 2 Dec, 2020
Next Greater Element
Easy
Asked in companies
You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return 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 'ARR', which is greater than ‘X’. If no such element exists to the right of ‘X’, then return -1.
For example:
For the given array 'ARR' = [7, 12, 1, 20]
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, the output is [12, 20, 20, -1].
Input Format:
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains an integer 'N' representing the size of the array/list 'ARR'.
The second line of each test case contains 'N' single space-separated integers representing the elements of the given array/list ‘ARR’.
Output Format :
For each test case, print 'N' single space-separated integers representing the Next Greater Element for each element.
Note
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 100
1 <= N <= 5 * 10^3
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
We will iterate through all the elements to their right and check if the element is greater than the current element. If we found the greater element, we will stop iteration for this element and move to the next element.
The steps are as follows:
- Initialize an array ‘ANS’ of integer type and size ‘N’ to store the next greater element of each element in the array.
- Fill the ‘ANS’ array with -1.
- Iterate through the given array ‘ARR’.(say, iterator = ‘i’)
- Iterate through the array ‘ARR’ from ‘i+1’ to the size of ‘ARR’. (say, iterator = ‘j’)
- If ‘ARR[j]’ is greater than ‘ARR[i],’ then update ‘ANS[i]’ as ‘ARR[j]’ and break the loop.
- Iterate through the array ‘ARR’ from ‘i+1’ to the size of ‘ARR’. (say, iterator = ‘j’)
- Return the ‘ANS’ array.
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.
The steps are as follows:
- Initialize an array ‘ANS’ of integer type and the same size as the input array to store the Next Greater Elements.
- Declare a stack ‘S’ of integer type that will have Next Greater Element as its top element.
- Iterate the array in reverse order. (say, iterator = ‘i’)
- Pop from ‘S’ until the stack ‘S’ is not empty and the current element is greater than the top element of the stack
- Update ‘ANS[i]’ with the top element of ‘S’.
- If the stack is empty then update ‘ANS[i]’ with -1.
- Push the current element onto the stack ‘S’.
- Return ‘ANS’.