# Next Greater Element

Posted: 16 Oct, 2020

Difficulty: Moderate

#### 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.
```

##### Note :

```
You are not required to print the expected output, it has already been taken care of. Just implement the function.
```

##### Constraints :

```
1 <= T <= 10
1 <= N <= 10^5
0 <= ARR[i] <= 10^9
Time Limit: 1sec
```

Approach 1

- 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.

Approach 2

- Initialise an array ans of length N to store the next greater number of arr[i] at index i.
- Create a stack of type integer, where we will store the smaller element at the top.
- Traverse the array from backwards, because when we will arrive at a certain index its next greater element will be already in the stack and we can easily get this element.
- For every element at index I,
- We will pop the elements from the stack till we get the greater element on top of the stack from the current element and that element will be the answer for the current element.
- If the stack gets empty while doing the pop operation then the answer would be -1.
- Store the next greater element in the array and.
- Push the current element of the array into the stack.

- Finally, return the array ans.

SIMILAR PROBLEMS

# Magical String

Posted: 27 Apr, 2021

Difficulty: Easy

# Span of Ninja Coin

Posted: 27 Apr, 2021

Difficulty: Moderate

# Queries on Stack

Posted: 28 Apr, 2021

Difficulty: Moderate

# PostFix To Prefix

Posted: 24 Jun, 2021

Difficulty: Easy

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy