Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 2 Dec, 2020

Next Greater Element

Easy
Asked in companies
MicrosoftAmazonPaytm (One97 Communications Limited)

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

Approaches

01 Approach

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.