Explain Monotonic Stack. What problems does it solve?

Difficulty: 7/10

Stack, Array Processing, Time Complexity Optimization

Monotonic Stack

A Monotonic Stack is a Stack maintained in either increasing or decreasing order. When a new element violates that ordering, elements are popped until the invariant is restored. This allows us to efficiently find relationships between an element and the nearest greater or smaller element.

javascript

1
Common problem: Next Greater Element.
2
Common problem: Next Smaller Element.
3
Useful for Daily Temperatures.
4
Useful for Largest Rectangle in Histogram.
5
Useful for stock span and nearest greater/smaller element problems.
6
Each element is pushed and popped at most once, giving O(n) total time.

Scenario Questions

0-2 years experience

1We are building a simple weather dashboard. Given an array of daily temperatures, how would you efficiently find how many days you have to wait for a warmer day for each day? Walk me through how you'd track this without using a nested loop.
2Imagine you have an array of building heights. You want to find the first building to the right that is taller than the current one. If we use a stack to keep track of the indices, what exactly happens to the stack when we encounter a building that is shorter than the one at the top of the stack?

Follow-up Questions

How would you modify your approach if the array was circular?
What is the space complexity of your solution, and can we optimize it if the input is already partially sorted?
How do you handle duplicate values in the stack—should we use strict inequality or non-strict?