Problem: Given an array of numbers, for each element find its next greater element.
Stack based solution:
For each element in the array:
- While current element is greater than top of stack, pop the stack and we have that the current element is the next greater element of the element we just popped.
- Push the current element onto the stack.
When we reach the end of the array, we know that all the elements left in the stack don’t have a next greater element.
The property we want to prove is that for each element in the stack, we will pop it off exactly when we find the first element that is greater than it.
To prove this we need to know that the stack is always sorted with the top of the stack being the smallest element. To see this, we use the fact that every time a new element is pushed onto the stack, it must be smaller than the current top of the stack, since if it is bigger than the top of the stack then the top of the stack gets popped until it is no longer greater than the top of the stack.
Now we consider 2 cases:
- The current element c is not greater than the element e in the stack. Since c is not greater than e, then e cannot popped and the property holds.
- The current element c is greater than the element e in the stack. Now, using the fact that the stack is sorted, that means all the elements above the element e are smaller than e, and therefore smaller than c. This means all those elements above e get popped, and then since c is greater than e, e will also get popped.
Therefore, for any element e in the stack, it is popped exactly when the current element is its next greater element.
Next we want to prove that it uses O(n) time.
For each element in the array, it is pushed and popped exactly once, so the number of push and pop operations is O(n).
Now, the other operation we want to prove is O(n) is comparisons.
To see this, note that for every element in the array, we start comparing to the top of the stack, and if it’s greater than the top of the stack then we pop and continue, if it’s not then we push and stop comparing. Therefore the number of comparisons is just one more than the number of pops. Since we know the number of pops is O(n), then the number of comparisons is also O(n).
Since all operations, push, pop, and compare are O(n), the overall time complexity is O(n).