Next Greater Element

Moderate

0/80

Average time to solve is 20m

153 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
4
1 2 4 3

Sample Output 1 :

2 4 -1 -1

Sample Input 2 :

1
4
9 3 6 5

Sample Output 2 :

-1 6 -1 -1

Explanation for Sample Input 2 :

For element 9, there is no next greater element. So -1 would be the next greater element.
For element 3, 6 is the next greater element. 
For element 6, there is no next greater element. So -1 would be the next greater element.
For element 5, there is no next greater element. So -1 would be the next greater element.

Hint 1

Hint 2

Find out the next greater number of each element of the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N^2), where N is the length of the given array.

In the worst case, we will be searching for the next greater element of each element. For searching the next greater element in arr it can take O(N) time, thus total time would be O(N^2).

Space Complexity

O(1).

In the worst case, only a constant extra space is required.

(75% EXP penalty)

(100% EXP penalty)

Next Greater Element

Console