Introduction

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Examples:

  1. For any array, rightmost element always has next greater element as -1.
  2. For an array which is sorted in decreasing order, all elements have next greater element as -1.
  3. For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1
Example Case

Approach

We use the Stack based approach to find the next greater element.

  1. Fill the next greater element array to -1
  2. Loop over the elements and perform the below operations
    i. Push the index to stack if stack top is greater than the current element
    ii. Loop and Pop until the stack top is less than the current element, and update the popped index with the current element

Code

using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
    public static void Main()
    {
        var t = int.Parse(Console.ReadLine() ?? "0");
        while (t-- > 0)
        {
            var n = int.Parse(Console.ReadLine() ?? "0");
            var a = Console.ReadLine()
                ?.Split(" ", StringSplitOptions.RemoveEmptyEntries)
                .Select(long.Parse).ToArray();
            var res = NextLargerElement(a, n);
            Console.WriteLine(string.Join(" ", res));
        }
    }
    static long[] NextLargerElement(long[] a, int n)
    {
        var res = new long[n];
        Array.Fill(res, -1);
        var st = new Stack<long>();
        st.Push(0);
        for (var i = 1; i < n; i++)
        {
            while (st.Count > 0 && a[i] > a[st.Peek()])
            {
                res[st.Pop()] = a[i];
            }
            st.Push(i);
        }
        return res;
    }
}
C# Code using Stack

References

https://www.geeksforgeeks.org/next-greater-element/