This is an interesting problem I found on geeksforgeeks .
You are given an array of integers. For each element in that array, you need to find the position of next element greater than it.
The above problem can easily be solved in O(n*n) using the naive algorithm. The naive algorithm involves checking the greater element for each element in O(n). Thus , the complexity for the entire algorithm becomes O(n*n).
However the above algorithm is too slow and requires optimization.
So,Here’s a O(n) approach using stacks.
Start by traversing the array and maintaining a stack. Initially the stack is empty denoted by top = -1.
You will push an element and increment the array pointer into the stack if –
- The stack is empty
- The element in the array is lesser than the top element of the stack.
You will pop the element (but do not increment the array pointer) if –
- The element in the array is greater than the top element of the stack.(This time you’ve found the element greater for the top element of the stack therefore you also mark the result).
Consider the following input – n = 4 , a = [3,2,4,1]
- Initially the stack is empty. So , top = -1.Also i(array pointer) = 0.
- Since the stack is empty,push the first element and increment the i. The top element in the stack becomes 3.
- The next element i.e 2 is lesser than the top element of the stack i.e 3. So,push it as well and increment i.The top element in the stack becomes 2.
- The next element i.e 4 is greater than the top element of the stack. We’ve got the greater element for top element of the stack.Therefore mark the result and pop out the top element.(Do not increment array pointer).The top element is now 3.
- the array element 4 is greater than the top element of the stack i.e 3.Therefore mark the result pop the top element and continue.
- Since the stack is empty now,push the array element 4.increment array pointer.
- the next element is 1 (smaller than top element of stack).So,push it and increment i.
- i=n , End of loop.
- Since the last two elements in the array aren’t marked in the loop,it means that there exists no such result for these values.(The default values are set as -1).
The above code produces the following output for the sample example-
Analysis of Complexity – O(n)
Consider any case, the above code involves pushing and popping each element into the stack exactly once.
Thus, the complexity is O(n) which is a big improvement over the previously discussed naive algorithm.
For any query , drop a comment below.