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

0heading

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

2heading
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

9heading

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?

11heading
.
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?

15heading

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

17subheading
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 = [0]*n stack = [0] 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

22subheading
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. .
24image

In the given sequence we start looking at the taller bar on the right, same as previous problems. But we now also have to take care of lower bounds to have accurate width. We initialize the stack with -1 index, so that when we are given only one bar, the maximum area will be the height of that bar. Also add 0 height to the sequence so we can take the last element into consideration.

25paragraph
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
26code