Possibly one of the most confusing, yet useful ideas for problem solving in coding interviews is the monotonic stack. In this video, we're going to show you an example and summarize it, so make sure to stick to the end. The monotonic stack is, as you might have guessed, a stack, which uses some greedy logic to keep the elements in the stack orderly after each new element is put onto the stack.
What kind of order are we talking about? It could be either monotonically increasing, which means the elements either increase or stay the same as we go left to right, or monotonically decreasing, which means that it either decreases or stays the same as we go left to right. Let's look at an example.
Given the heights of five people, find the height value of the person with the next largest height. If there is no larger height, store negative one. Let's think about the brute force solution first.
For each height, iterate through the rest of the array to find out the next greater height. The time complexity would be O of n squared, but do we really need to loop through the entire rest of the array? We're going to iterate from right to left and use a monotonic stack to keep the higher people on your right. In this case, we're going to be maintaining a monotonically decreasing stack. Every time we put an element into the stack, we still want to make sure that the stack is monotonically decreasing.
We have 2, 1, 2, 4, and 3. So of course, once again, we're going to be moving from right to left, and we're going to have our stack which maintains the greater values than the current height. So for example, if we were to deal with this 3 here, and this 3 pertains to this person in the blue on the right here, we see that the stack is empty. If the stack is empty, that basically means that okay, nothing is greater than three so far. So what that means is we can just assign this value negative one, which means that the greatest height so far, or the greatest height on the right side of this person is nothing, meaning it's negative one. So in that case, let's just put the three into our monotonic stack.
And remember, this is a decreasing monotonic stack. Next, let's deal with this number four. And this four pertains to this red person here.
And so if we were trying to put in this four here, we're once again, we're trying to maintain a monotonically decreasing stack, meaning the smaller elements are at the top and the larger elements are at the bottom. If we were trying to put this four into here, that would break our invariant. So what we need to do is we need to take this three out. And then finally, we see that the stack is empty, meaning that nothing is greater than this four on the right side. So but the negative one here, meaning that nothing to the right is greater than this four.
So let's put this four into our monotonic stack. Next, let's deal with this two here, which pertains to this green person. Obviously, we can see that the answer for this is going to be four, because the person of height four is greater than this person of height two.
And so what we can do is we realize, okay, four is the top of our stack, which means that this is the next greatest element. greater than this two. So we can easily just put the four here, which is our answer.
And we can put two into our monotonic stack. Because then when we deal with the next person, which is a person height one, we can see, okay, the person at the top of the stack is the first person that's greater than this, right? That's why we're keeping these elements in here in a monotonically decreasing order.
So let's put this element into here. And we see that the top elements are two. So that's our answer for two.
And we maintain our invariance, which is just going to be decreasing. So we can just put the one into our monotonic stack. And finally, let's deal with this yellow person here, which is of height two, we want to put this into our stack.
But we want to find the first person that's strictly greater than this two, right? So what we're going to do is we want to maintain the invariance. So we take out the one, okay. But this is still not decreasing, strictly decreasing. So we need to take this two out.
And then finally, we see that we can successfully put the four or this two inside. And the top element is going to be the four, meaning that the answer in this case, is going to be four. So we put the two in.
And that's our final stack. We're done here. And we see that we finished all the items.
And this is the answer for our specific case. So what does the code look like for the next greater element problem, what our function does is takes in a array of heights. And what we're going to do is create an array of integers, as well as a monotonic stack, this could just be implemented as a regular stack, we're going to look through the elements from the right side all the way to the left side. And what we're going to say is while our stack is not empty, and the element at the top of the stack is less than or equal to the current height that we want to insert, then pop the stack. Next, what we want to do is check if the current stack is empty.
If it is empty, then we just say that the answer is negative one for the current element, because nothing is greater than it. And otherwise, the element... at the top of the stack is going to be the answer for the ith element.
Then simply we want to push our element into the stack because we know it's going to maintain the invariant. Finally return the answer. The reason that all of this works is because the monotonic stack stores both the position and magnitude of the values. The position is stored by the order in the stack and the magnitude is stored by popping stuff off of the stack.
And that's exactly why we're able to achieve this O complexity. Otherwise, we would have an O of n squared. That's it for the monotonic stack. If you liked this video, like, comment, and subscribe.