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 \).
You are given \( N \), the number of elements, followed by \( N \) space-separated integer values.
- \( 2 \leq N \leq 10^6 \)
Array values are 32bit integers.
For each element of the array \( arr_i \) print its NGE, in the same order of the array.
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.
Instead of using a dictionary (
std::unordered_map in the example above), we
can store result at the index. Just put in the stack the pair index/value as
in the example below:
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
Here is the idea:
- we iterate backwards from the second-last element (the last does not have NGE1). Say this is index
i. Also, put
nums[j](the next one) is greater than
nums[j](the next one) is less than
nums[i], then we compare
nums[indices[j]]- that is the NGE of
nums[j]. Let’s update
- 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
Basically, indices is used to “jump” through NGEs.
A visual example follows.
Suppose we have the input array:
10 3 6 5 20.
Starting from the end of the array, we process
Since (( 5<20 )) we know that
20 is NGE of
Then we process
This time (( 6>5 )) then we use replace
5 with its NGE -
Such a value is greater than
6 thus we have found NGE for
Now we have
Since (( 10>3 )) we “jump” to
3's NGE, that is
6. Again, (( 10>6 )) so we jump to
6's NGE, that is
Since (( 20>10 )) we have found NGE for
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.