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 | 0 | heading |
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). | 1 | paragraph |
Intuition for Monotonic Stack | 2 | heading |
 | 3 | image |
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? | 4 | paragraph |
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) | 5 | code |
That's where the monotonic stack comes in: | 6 | paragraph |
Promoted Promoted
| 7 | list |
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 | 8 | code |
How to use Monotonic Stack | 9 | heading |
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. | 10 | paragraph |
What happens if people are standing in a circle? | 11 | heading |
 | 12 | image |
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. | 13 | paragraph |
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 | 14 | code |
Where can we use Monotonic Stack? | 15 | heading |
Once we understand the framework for monotonic stack we can use it for various problems. Few examples are given below | 16 | paragraph |
Find the next warmer day from today | 17 | subheading |
| LeetCode 739. Daily Temperatures | 18 | link |
 | 19 | image |
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. | 20 | paragraph |
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] | 21 | code |
Largest Rectangle in Histogram | 22 | subheading |
| 84. Largest Rectangle in Histogram | 23 | link |
 | 24 | image |
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. | 25 | paragraph |
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 | 26 | code |