DSA · Chapter 16 of 40
Monotonic Stack
A monotonic stack keeps its elements in increasing or decreasing order by popping anything that breaks the order before pushing. It answers 'next greater element' style questions in O(n).
Each element is pushed and popped at most once, which is why the total work stays linear even though there is a while loop inside a for loop.
Next greater element
Scan right to left with a decreasing stack: pop everything smaller than the current value, then the top is the next greater element.
Other uses
Largest rectangle in a histogram, stock span, and daily temperatures all use monotonic stacks.
Example 1 (python)
def next_greater(nums):
res = [-1] * len(nums)
stack = []
for i in range(len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
print(next_greater([2, 1, 3]))Output
[3, 3, -1]Each element enters and leaves the stack once, so it is O(n).
Example 2 (python)
def days_to_warmer(temps):
res = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
res[j] = i - j
stack.append(i)
return res
print(days_to_warmer([73, 74, 75, 71]))Output
[1, 1, 0, 0]Storing indices lets us compute distances.
Key points
- A monotonic stack keeps a sorted order by popping violators.
- Next greater / previous smaller problems become O(n).
- Store indices when you need distances.
- Amortised analysis explains the linear time.
💡 Note: Explain that each element is pushed and popped once — that is the key insight interviewers look for.