Next Greater Element
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

Question

Next Greater Element

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

Accepted Answer

The task is to find the next greater element for each element in an array.

Iterate through the array from right to left
Use a stack to keep track of the elements
For each element, pop elements from the stack until a greater element is found or the stack is empty
If a greater element is found, it is the next greater element for the current element
If the stack becomes empty, there is no greater element to the right
Store the next greater element for each element in a result array

Accepted Answer

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:

Initialize an array ‘ANS’ of integer type and size ‘N’ to store the next greater element of each element in the array.
Fill the ‘ANS’ array with -1.
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.
Return the ‘ANS’ array.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is used.

Time Complexity: O(n^2)Explanation:

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

Java (SE 1.8)

/*

    Time Complexity - O(N^2)
    Space Complexity - O(1)

    where N is the number of elements in the array/list.

*/

import java.util.*;

public class Solution {
    public static ArrayList nextGreaterElement(ArrayList arr, int n) {
        ArrayList ans = new ArrayList();

        for (int i = 0; i < n; i++) {
            ans.add(-1);
        }

        for (int i = 0; i < n; i++) {

            // Traverse from next index to end.
            for (int j = i + 1; j < n; j++) {

                /*
                    As soon as we find a greater element, we'll update the 'ans[i]' and break the
                    loop.
                 */
                if (arr.get(j) > arr.get(i)) {

                    ans.set(i, arr.get(j));
                    break;
                }
            }
        }

        return ans;
    }
}

Python (3.5)

'''



    Time Complexity - O(N^2)

    Space Complexity - O(1)



    Where N is the number of elements in the array/list.



'''





def nextGreaterElement(arr, n):

    

    ans = [-1] * n



    for i in range(n):

        

        # Traverse from next index to end.

        for j in range(i + 1, n):

            '''

                As soon as we find a greater element,

                we'll update the 'ans[i]' and break the loop.

            '''

            if arr[j] > arr[i]:

                ans[i] = arr[j]

                break



    return ans

C++ (g++ 5.4)

/*



    Time Complexity - O(N^2)

    Space Complexity - O(1)



    where N is the number of elements in the array/list.



*/



vector nextGreaterElement(vector& arr, int n) {



  vector ans(n, -1);



  for (int i = 0; i < n; i++) {



      // Traverse from next index to end.

      for (int j = i + 1; j < n; j++) {

        

          /* 

              As soon as we find a greater element,

              we'll update the 'ans[i]' and break the loop. 

          */

          if (arr[j] > arr[i]) {

              ans[i] = arr[j];

              break;

          }

      }

  }



  return ans;

}

Accepted Answer

Using Stack

We will use a Stack to keep track of the next greater element and pop as soon as we find an element greater than it.

The steps are as follows:

Initialize an array ‘ANS’ of integer type and the same size as the input array to store the Next Greater Elements.
Declare a stack ‘S’ of integer type that will have Next Greater Element as its top element.
Iterate the array in reverse order. (say, iterator = ‘i’)
1. Pop from ‘S’ until the stack ‘S’ is not empty and the current element is greater than the top element of the stack
2. Update ‘ANS[i]’ with the top element of ‘S’.
3. If the stack is empty then update ‘ANS[i]’ with -1.
4. Push the current element onto the stack ‘S’.
Return ‘ANS’.

Space Complexity: O(n)Explanation:

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

In the worst case, the stack can hold all the array elements. Hence space complexity is O(N).

Time Complexity: O(n)Explanation:

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

When the array is given in decreasing order, then for every element in the array -

We push it onto the stack.
It gets popped at the next iteration by a greater element

Hence, in the worst case, every element in the array gets pushed and popped into the stack at most once. Thus, the time complexity is O(N).