Monotonic Stack Pattern
Apply the monotonic stack to solve daily-temperatures, largest-rectangle-in-histogram, and next-greater-element in O(n).
Monotonic Stack Pattern is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is a Monotonic Stack?
A monotonic stack is a stack that maintains a sorted invariant across its elements. An increasing monotonic stack has elements increasing from bottom to top; a decreasing monotonic stack has elements decreasing from bottom to top. When a new element violates the invariant, elements are popped until the invariant is restored, and then the new element is pushed.
This simple mechanism enables O(n) answers to 'nearest greater element' and 'nearest smaller element' queries that would naively require O(n²) nested loops.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Next Greater Element (LeetCode 496)
For each element, find the first element to its right that is strictly greater. A brute force O(n²) scans rightward from each position. The monotonic stack approach: maintain a decreasing stack of indices. When a larger element is encountered, pop all smaller indices — their 'next greater' is the current element. Remaining indices have no next greater element (answer is -1).
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Next Greater Element in Circular Array
LeetCode 503 'Next Greater Element II': same problem but the array is treated as circular. After reaching the end, wrap around and check from the beginning. The trick: iterate through the array twice (indices 0 to 2n-1) and use i % n to index into the original array. Only push indices in the range [0, n-1] to avoid duplicate processing.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Daily Temperatures: Full Solution
LeetCode 739 revisited: for each day, how many days until a warmer temperature? The monotonic stack holds indices of days with temperatures in decreasing order. When a warmer day i is found, pop all cooler-day indices j from the stack and record result[j] = i - j. Days remaining in the stack never found a warmer day, so their result stays 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Previous Smaller Element
The 'previous smaller element' query asks: for each element, what is the nearest smaller value to its left? Use an increasing monotonic stack processing left to right. Before pushing index i, the top of the stack is the previous smaller element (because all elements larger than nums[i] were already popped during previous insertions that triggered larger elements to pop them).
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Largest Rectangle in Histogram
LeetCode 84 'Largest Rectangle in Histogram': a monotonic increasing stack of indices. For each bar, pop all bars taller than the current one. For each popped bar h, its right boundary is the current index i and its left boundary is the new stack top + 1 (or 0 if the stack is empty). Area = h × (right - left). Append a 0-height sentinel to force all remaining bars to be popped at the end.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Maximal Rectangle (LeetCode 85)
LeetCode 85 'Maximal Rectangle' extends the histogram problem to a 2D binary matrix. For each row, compute the accumulated bar heights: if matrix[row][col] == '1', height is the number of consecutive 1s above and including this cell. Then apply the 'largest rectangle in histogram' algorithm to each row's heights array. Time: O(m × n) for an m×n matrix.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Trapping Rain Water: Stack Approach
LeetCode 42 'Trapping Rain Water' with a stack: maintain a decreasing stack of indices. When a taller bar is encountered, a valley forms. Pop the valley bottom; calculate water width as (current_index - stack_top - 1) and height as (min(current_bar, new_stack_top_bar) - valley_height). Sum all contributions. Time: O(n), Space: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Recognising Monotonic Stack Problems
Signals that a monotonic stack is the right tool: the problem asks for the next or previous greater/smaller element, the answer for each element depends on elements in a specific direction, or a naive O(n²) solution involves scanning left or right for each element. The stack stores candidates that might be answers for future elements and discards them as soon as a better candidate arrives.
Always decide upfront: increasing (for next/previous smaller) or decreasing (for next/previous greater) and from which direction you process.
Amortised O(n) Analysis
Monotonic stack algorithms appear O(n log n) or O(n²) at first because of the while loop inside the for loop. But each element is pushed at most once and popped at most once. The total number of push operations equals n, and the total number of pop operations is also at most n. So across all iterations the total work is 2n operations — O(n) amortised, not O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nSummary: Monotonic Stack Invariant Choices
Choose the stack direction based on the query. For next greater element, use a decreasing stack — pop when current element is larger. For next smaller element, use an increasing stack — pop when current element is smaller. For largest rectangle, use an increasing stack and pop when a shorter bar appears. For sliding window max, use a decreasing deque and remove from both ends.
Writing the invariant in a comment before coding clarifies the logic and speeds up debugging.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a monotonic stack maintains a sorted invariant by popping elements that violate it before pushing the new element, decreasing stacks answer next-greater-element queries; increasing stacks answer next-smaller-element queries, and total time is O(n) amortised because each element is pushed and popped at most once. Next up we implement queues using stacks and stacks using queues.
Frequently asked questions
Is the “Monotonic Stack Pattern” lesson free?
Yes — the full text of “Monotonic Stack Pattern” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Monotonic Stack Pattern”?
Apply the monotonic stack to solve daily-temperatures, largest-rectangle-in-histogram, and next-greater-element in O(n). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Monotonic Stack Pattern” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.