Next Greater Element

Easy
0/40
Average time to solve is 10m
profile
Contributed by
186 upvotes
Asked in companies
FlipkartAmazonGroww

Problem statement

You are given an array 'a' of size 'n'.



The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.


If no greater elements exist to the right of 'x', consider the next greater element as -1.


For example:
Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- 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 we consider NGE as -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains an integer 'n' representing the size of the array.

The second line of input contains 'n' single space-separated integers representing the elements of the array.


Output Format :
The only line of output contains 'n' single space-separated integers representing the Next Greater Element for each element. 


Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
5
1 5 3 4 2


Sample Output 1:
5 -1 4 -1 -1


Sample Input 2:
5
5 5 5 5 5


Sample Output 2:
-1 -1 -1 -1 -1


Expected time complexity :
The expected time complexity is O(n).


Constraints :
1 <= 'n' <= 10^5
1 <= 'a[i]' <= 10^9

Time Limit: 1 sec
Hint

For every element, traverse its right side and try to find a greater element.

Approaches (2)
Brute Force

For every element in the array, we will run a loop on its right side. As soon as we find an element on its right side which is greater than it, we will break the loop, assign it as the NGE of this element, move forward, and do the same for the next element.

Time Complexity

O(n ^ 2),  Where 'n' is the number of elements in the array.

For every element, we will be checking nearly every other element in the array, hence time complexity is quadratic.

Space Complexity

O(1)

Constant extra space is used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Next Greater Element
Full screen
Console