See the original problem on HackerRank.
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 \).
Input Format
You are given \( N \), the number of elements, followed by \( N \) spaceseparated integer values.
Constraints
 \( 2 \leq N \leq 10^6 \)
Array values are 32bit integers.
Output Format
For each element of the array \( arr_i \) print its NGE, in the same order of the array.
Solutions
The naive solution consists in using two loops: for each element we find the next greater element. This solution is quadratic because for each element we pay a linear search.
The worst case is when the array is sorted in decreasing order.
Linear solution using stack
We could optimize by using a stack:
 push the first element to the stack;
 process the second element;
 if the top of the stack is greater/equal than the current number then add that number to the stack;
 if the top of the stack is less than the current number then keep on popping elements from the stack until the top of the stack is greater/equal to the current number OR the stack gets empty. The current number is the NGE of all the elements popped from the stack;
 if the stack is not empty at the end of all iterations, mark the NGE of remaining items in stack as 1.
Here is an implementation in C++:


We put elements in a vector just for convenience  we could have processed elements straight from the input.
Since the output has to be in order, we need an additional data structure to maintain the results. We used a map but we can use a vector, getting very likely better performance.
Variation: what if the array has duplicates? Although the core idea still holds, the way we store NGEs needs to be changed a bit.
Linear solution using an index array
Instead of storing NGEs, we can instead store their indices in a vector indices
.
Here is the idea:
 we iterate backwards from the secondlast element (the last does not have NGE1). Say this is index
i
. Also, putj=i+1
;  if
nums[j]
(the next one) is greater thannums[i]
, thennums[j]
isnums[i]
’s’ NGE;  if
nums[j]
(the next one) is less thannums[i]
, then we comparenums[i]
withnums[indices[j]]
 that is the NGE ofnums[j]
. Let’s updatej=indices[j]
 we repeat the previous step until we fall into step 2 or we find 1
indices contain all the indices of NGEs (or 1) for each number
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
int n; cin >> n; vector<int> nums(n); copy_n(istream_iterator<int>(cin), n, begin(nums)); vector<int> indices(nums.size(), 1); for (int i = nums.size()  2; i >= 0; i) { auto j = i + 1; while (j != 1 && nums[j] <= nums[i]) j = indices[j]; indices[i] = j; } for (auto i : indices) { cout << (i==1 ? 1 : nums[i]) << " "; }
Basically, indices is used to “jump” through NGEs.
A visual example follows.
Suppose we have the input array: 10 3 6 5 20
.
We initialize indices
with 1
:
Starting from the end of the array, we process 5
and 20
:
Since (( 5<20 )) we know that 20
is NGE of 5
:
We update indices
:
Then we process 6
and 5
:
This time (( 6>5 )) then we use replace 5
with its NGE  20
:
Such a value is greater than 6
thus we have found NGE for 6
:
Now we have 10
and 3
:
Since (( 10>3 )) we “jump” to 3
’s NGE, that is 6
. Again, (( 10>6 )) so we jump to 6
’s NGE, that is 20
:
Since (( 20>10 )) we have found NGE for 10
:
That’s it!
Although are both linear, this solution may be slightly faster than the previous one because the index array is contiguous and not dynamic. This could result in a better usage of the memory and the cache. In addition, we don’t need extra space to keep results in order.
If we vary the problem by introducing duplicates, this solution is already capable of handling the new requirement since indices
(aka: NGE indices) is positional.