How do you find the next greater element for every position in an array?
You use a stack and you keep the values in it in decreasing order. The stack holds the positions whose next greater element you have not found yet.
def next_greater(values):
result = [-1] * len(values)
stack = []
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
result[stack.pop()] = value
stack.append(i)
return result
So how does it work? You walk through the array from left to right. At each position you ask a question about the values that are waiting in the stack. Is the current value greater than the one on top of the stack? If it is then the current value is the next greater element for that waiting position, so you write the answer and you take it off the stack. And you keep doing that until the stack is empty or the current value is not greater than the top.
And then you put the current position on the stack, because its next greater element has not been found yet.
the values the stack what happens
------------ ---------- --------------------------
[2, 1, 5] [] push the position 0
[2, 1, 5] [0] 1 is not greater than 2, push
[2, 1, 5] [0, 1] 5 is greater than 1, answer 5
[2, 1, 5] [0] 5 is greater than 2, answer 5
the answer [5, 5, -1]
And why does the stack keep the values in decreasing order? Because if the top of the stack were smaller than the one below it, then the top would have been answered already when the bigger one arrived. So the stack is always decreasing from the bottom to the top, and that means the top is always the smallest waiting value, which is the one most likely to be beaten by the current value.
And the complexity is O of n for the time, because every position goes onto the stack once and comes off once, and O of n for the space.
So the rule to remember is this. The stack holds the unanswered positions in decreasing order, and the current value answers everything on the top that is smaller than it.
The next two questions in this topic show the slow version and the circular version.