Next Greater Element
Posted: 16 Oct, 2020
You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.
For Example :
If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.
Input Format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains an integer N, representing the length of the input array(ARR). The second line contains N single space-separated integers representing elements of the array arr.
Output Format :
For each test case, print a list of integers each representing the NGE(next greater element) of each element of the given array in a single line.
You are not required to print the expected output, it has already been taken care of. Just implement the function.
1 <= T <= 10 1 <= N <= 10^5 0 <= ARR[i] <= 10^9 Time Limit: 1sec
- Initialise an array ans of length N to store the next greater number of arr[i] at index i.
- Traverse the given array and for every element at index I
- Initialise a variable next to -1.
- Run a loop from i+1 to N, and check whether the current element is greater than arr[i] then update the next to the current element and break the loop.
- Store next at ans[i].
- Return ans array.