Approach #1 Brute Force (using Double Length Array) [Time Limit Exceeded]
In this method, we make use of an array which is formed by concatenating two copies of the given array one after the other. Now, when we need to find out the next greater element for , we can simply scan all the elements , such that . The first element found satisfying the given condition is the required result for . If no such element is found, we put a at the appropriate position in the array.
Time complexity : . The complete array(of size ) is scanned for all the elements of in the worst case.
Space complexity : . array of size is used. array of size is used.
Approach #2 Better Brute Force [Accepted]
Instead of making a double length copy of array , we can traverse circularly in the array by making use of the operator. For every element , we start searching in the array(of length ) from the index and look at the next(cicularly) elements. For we do so by scanning over , such that , and we look for the first greater element found. If no such element is found, we put a at the appropriate position in the array.
Time complexity : . The complete array of size is scanned for all the elements of in the worst case.
Space complexity : . array of size is used.
Approach #3 Using Stack [Accepted]
This approach makes use of a stack. This stack stores the indices of the appropriate elements from array. The top of the stack refers to the index of the Next Greater Element found so far. We store the indices instead of the elements since there could be duplicates in the array. The description of the method will make the above statement clearer.
We start traversing the array from right towards the left. For an element encountered, we pop all the elements from the stack such that . We continue the popping till we encounter a satisfying . Now, it is obvious that the current only can act as the Next Greater Element for (right now, considering only the elements lying to the right of ).
If no element remains on the top of the stack, it means no larger element than exists to its right. Along with this, we also push the index of the element just encountered(), i.e. over the top of the stack, so that (or ) now acts as the Next Greater Element for the elements lying to its left.
We go through two such passes over the complete array. This is done so as to complete a circular traversal over the array. The first pass could make some wrong entries in the array since it considers only the elements lying to the right of , without a circular traversal. But, these entries are corrected in the second pass.
Further, to ensure the correctness of the method, let's look at the following cases.
Assume that is the correct Next Greater Element for , such that . Now, whenever we encounter , if , it would have already popped the previous and would have become the topmost element. On the other hand, if , it would have become the topmost element by being pushed above the previous . In both the cases, if , it will be correctly determined to be the Next Greater Element.
The following example makes the procedure clear:
As the animation above depicts, after the first pass, there are a number of wrong entries(marked as ) in the array, because only the elements lying to the corresponding right(non-circular) have been considered till now. But, after the second pass, the correct values are substituted.
Time complexity : . Only two traversals of the array are done. Further, atmost elements are pushed and popped from the stack.
Space complexity : . A stack of size is used. array of size is used.
Analysis written by: @vinod23