Promoted
Promoted

## Monotonic Stack

Stack is one of the popular data structures used in a lot of algorithms like backtracking, depth-for-search(DFS), reverse string, undo/redo, call stack and many more. There are many forms of stacks such as Min Stack - which gives the minimum number in stack in constant time O(1). Max Stack - which gives the maximum number. Other than that there is a monotonic stack. It is called monotonic because the order in the stack is either increasing or decreasing.

### When to use Stack

Stack is mostly used in problem solving where you store partially solved problems(probably because there was interruption and you want to focus on different problems e.g. call stack, you don't have enough input to solve e.g. DFS, or traversing hierarchy e.g navigating folders in file system) only to be solved later in Last in First Order(LIFO).

1paragraph

### Intuition for Monotonic Stack Consider an example where 5 people with different heights are standing in line and one has to tell who is the next tallest person standing on the right side?.
3image

We can solve this problem by considering one person at a time and comparing heights of the person standing next to the right. That means for every person we have traversed once. So two find the answer we traverse n^2. Is there a way we can find out by going through each person once?

4paragraph
``` for current_person_height in heights: for person_on_right_height in heights: if current_person_height < person_on_right_height: print(“Tallest person on right height is ”, person_on_right_height)```
5code

That's where the monotonic stack comes in:

6paragraph

Promoted
Promoted

• We are going to store the height of the first person in the stack and loop through others.
• From second person onwards, we compare the current person's height with the height of the person at the top of the stack.
• If we found the current person is taller than the person at top of the stack we pop that person from the stack. Current person is taller than the person we just popped out.
• If the stack is still not empty we do the same comparison until the stack is empty or the current person is shorter.
• At the end of the loop we add the current person to stack. This way we traverse the list only once.
7list
``` height=[9,6,10,7,9] stack = [] #initialize stack result = [0,0,0,0,0] #initialize array to store positon of taller person on right stack.append(0) #add person standing at 0 position for current in range(1, len(height)): #iterate through from second person till last while stack and height[stack[-1]] < height[current]: #compare current person height with the height of the person at the top of the stack #current person is taller person for the person at top of stack result[stack.pop()] = current stack.append(current) print(result) #[2, 2, 0, 4, 0], No person is taller for 3rd person and there is no right for 5th person```
8code

### How to use Monotonic Stack

We can use the same monotonic Stack to find a short person to the right by changing comparison for less than to greater than. We can also change direction to find the tallest person on the left side by changing the for loop to iterate from last element to first.

10paragraph

### What happens if people are standing in a circle?

12image

Last person standing will be next to the first person. In this case we need to iterate all people one more time to find taller people for the last person. We can modify the above code by changing the for loop to go through the list twice. But that will mess up positions of person in second loop, so to correct it we apply mod to current position.

13paragraph

Promoted
Promoted

``` height=[9,6,10,7,9] stack = [] #initialize stack result = [0,0,0,0,0] #initialize array to store positon of taller person on right stack.append(0) #add person standing at 0 position for current in range(1, len(height)*2): #iterate through from second person till last while stack and height[stack[-1]] < height[current % len(height)]: #compare current person height with the height of the person at the top of the stack #current person is taller person for the person at top of stack result[stack.pop()] = current % len(height) stack.append(current % len(height)) print(result) #[2, 2, 0, 4, 2], 3rd person can see 2nd person now```
14code

### Where can we use Monotonic Stack?

Once we understand the framework for monotonic stack we can use it for various problems. Few examples are given below

16paragraph

#### Find the next warmer day from today Find the next warmer day from today.
19image

We can use the same framework as above. The only change here is since we have to record the number of days we have to wait, we take the difference of the index of the current temperature and the index of the temperature we popped out from the stack.

20paragraph

Promoted
Promoted

``` def dailyTemperatures(temperatures): n = len(temperatures) res = *n stack =  for current in range(n) while stack and temperatures[stack[-1]] < temperatures[current]: index = stack.pop() res[index] = current - index #difference of current index and index at top of stack stack.append(current) return res #result = [1,1,4,2,1,1,0,0]```
21code

#### Largest Rectangle in Histogram

``` def largestRectangleArea(heights): heights.append(0) #one more iteration to handle last element stack = [-1] maxArea = 0 n = len(heights) for i in range(n): while stack and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - 1 - stack[-1] #stack[-1] - 1 is lower bound maxArea = max(maxArea, h * w) stack.append(i) return maxArea #result 10```