Next Greater Element

Easy
0/40
Average time to solve is 10m
profile
Contributed by
87 upvotes
Asked in companies
AdobeGoldman SachsMakeMyTrip

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
4
13 7 6 12
Sample Output 1:
-1 12 12 -1
Explanation For Sample Output 1:
For the given array [13, 7, 6, 12].

There is no greater element for 13 on the right side.
The next greater element for 7 is 12. 
The next greater element for 6 is 12. 
There is no greater element for 12 on the right side.

So, the output is [-1, 12, 12, -1].
Sample Input 2:
2
5
1 2 3 4 5
3 
10 9 10
Sample Output 2:
2 3 4 5 -1
-1 10 -1
Hint

Can you find the next greater element by comparing it with the next elements.?

Approaches (2)
Brute Force

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:

 

  1. Initialize an array ‘ANS’ of integer type and size ‘N’ to store the next greater element of each element in the array.
  2. Fill the ‘ANS’ array with -1.
  3. Iterate through the given array ‘ARR’.(say, iterator = ‘i’)
    1. Iterate through the array ‘ARR’ from ‘i+1’ to the size of ‘ARR’. (say, iterator = ‘j’)
      1. If ‘ARR[j]’ is greater than ‘ARR[i],’ then update ‘ANS[i]’ as ‘ARR[j]’ and break the loop.
  4. Return the ‘ANS’ array.
Time Complexity

O(N^2),  where ‘N’ is the number of elements in the array/list.

 

For every element, we will be checking nearly every other element in the array. Hence time complexity is O(N^2).

Space Complexity

O(1).

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Next Greater Element
Full screen
Console