A monotonic stack is a stack whose elements always stay in sorted order, either increasing or decreasing, as you push and pop. Before pushing a new element, you pop everything that violates the order. This simple discipline lets you answer “what is the next greater element” or “what is the previous smaller element” for every position in a single linear pass.
When to use it#
Reach for a monotonic stack when the problem asks about the nearest element that is greater or smaller than the current one, on the left or right side. Signal words include next greater, next smaller, span, and “how far until.” If a brute-force solution compares each element to others in a nested loop, a monotonic stack usually collapses it to linear time.
Worked example#
Finding the next greater element for each item in an array:
1def next_greater(nums):
2 result = [-1] * len(nums)
3 stack = [] # holds indices, values are decreasing
4 for i, value in enumerate(nums):
5 while stack and nums[stack[-1]] < value:
6 result[stack.pop()] = value
7 stack.append(i)
8 return result
9
10print(next_greater([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
Each index is pushed once and popped at most once, so the work is linear even though there is a nested while loop.
Complexity#
Time is O(n) because every element enters and leaves the stack at most once. Space is O(n) for the stack in the worst case, such as a strictly increasing input.
Practice problems#
- Next Greater Element I and II
- Daily Temperatures
- Largest Rectangle in Histogram
- Trapping Rain Water
- Sum of Subarray Minimums
- Remove K Digits
Once this clicks, revisit the Big-O cheat sheet to see why the amortized cost stays linear, and continue with the pattern hub.