Monotonic Stack: Increasing vs Decreasing
Maintain an increasing or decreasing stack to efficiently answer next-greater-element and previous-smaller-element queries in O(n).
What Is a Monotonic Stack?
A monotonic stack is a stack that maintains a sorted order of its elements (either always increasing from bottom to top, or always decreasing). Before pushing a new element, we pop all elements that violate the monotonic invariant. This constrained structure enables O(n) solutions to problems that would otherwise require O(n²) nested loops.
The key insight: elements are pushed and popped at most once each, so the total number of operations across the entire array traversal is O(n) — not O(n²). The moment we pop an element, we have found the answer it was waiting for.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Next Greater Element I
The Next Greater Element problem: for each element, find the first element to its right that is greater. A brute-force O(n²) double loop is too slow. With a monotonic decreasing stack, we solve this in O(n).
Process elements left to right. Before pushing element i, pop all elements from the stack that are less than nums[i] — nums[i] is the next greater element for all of them. After processing all elements, any remaining items on the stack have no greater element to their right (answer = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]All lessons in this course
- Monotonic Stack: Increasing vs Decreasing
- Largest Rectangle in Histogram
- Sliding Window Maximum with Monotonic Deque
- Trapping Rain Water: Stack and Two-Pointer