New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Next Greater Element II

Contributed by

Ratnesh

Medium

0/80

Avg time to solve 35 mins

Success Rate 70 %

1 upvotes

Problem Statement

You have been given a circular array/list ‘ARR’ consisting of ‘N’ positive integers. (i.e., the next element of ‘nums[N - 1]’ is ‘nums[0]’)

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 we encounter while traversing ahead in the array circularly, which is greater than ‘X’. If no such element exists, then return -1.

Note: 1-based indexing is used for the explanations.

Example:

Input: [1,2,1]

Output: 2 -1 2

The first greater element next to 1 is 2.
There is no greater element next to 2 while traversing circularly, hence answer is -1.
The first greater element next to 1 is 2.

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

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains one integer 'N' denoting the size of array 'A'.

The second line of each test case contains 'N' single space-separated integers, elements of the array 'A'.

Output format :

For each test case, Return the Next Greater Element(NGE) for every element.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
0 <= A[i] <= 10ٰ^9

Time Limit: 1 sec

Sample Input 1 :

##### Sample Output 1 :

2 -1 2
2 3 4 -1 4

Explanation Of Sample Input 1 :

For the first case:

Input: [1,2,1]

Output: 2 -1 2

The first greater element next to 1 is 2(index 2).
There is no greater element next to 2 while traversing circularly, hence answer is -1.
The first greater element next to 1 is 2(index 2).


For the second case:

Input: [1,2,3,4,3]

Output: 2 3 4 -1 4

The first greater element next to 1 is 2(index 2).
The first greater element next to 2 is 3(index 3).
The first greater element next to 3 is 4(index 4).
There is no greater element next to 4 while traversing circularly, hence answer is -1.
The first greater element next to 3 is 4(index 3).

Sample Input 2 :

2
8
6 1 50 1 50 30 6 100
6
55 19 21 13 10 67

Sample Output 2 :

50 50 100 50 100 100 100 -1 
67 21 67 67 67 -1

Auto

Console