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).
Monotonic Stack: Increasing vs Decreasing is a free DSA Interview Prep lesson on CoddyKit — lesson 1 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 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]Next Greater Element: Tracing the Algorithm
Let us trace [2, 1, 2, 4, 3] step by step. We maintain a decreasing stack of indices whose next-greater element has not been found yet.
- i=0, val=2: stack empty, push 0. Stack: [0]
- i=1, val=1: 1 < nums[0]=2, push 1. Stack: [0,1]
- i=2, val=2: pop 1 (nums[1]=1 < 2), result[1]=2; now nums[0]=2 not < 2, push 2. Stack: [0,2]
- i=3, val=4: pop 2 (result[2]=4), pop 0 (result[0]=4), push 3. Stack: [3]
- i=4, val=3: 3 < nums[3]=4, push 4. Stack: [3,4]
- End: stack [3,4] have result=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Previous Smaller Element
Monotonic stacks also answer previous smaller element (PSE) queries: for each element, the nearest element to its left that is smaller. Instead of popping on a greater element, we pop on a greater-or-equal element and record the stack top as the PSE before pushing.
The direction changes: we still process left to right, but instead of answering questions as we pop, we answer questions just before pushing. The stack top at that moment is the nearest smaller element to the left. If the stack is empty, there is no smaller element to the left (answer = -1 or a sentinel).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Daily Temperatures: Waiting for Warmer Days
The Daily Temperatures problem (LeetCode 739): given daily temperatures, return an array where each element is the number of days until a warmer temperature. This is exactly the next-greater-element pattern, but instead of the greater value we want the number of days (index difference).
Use a monotonic decreasing stack of indices. When we find a warmer temperature at index i, pop all indices j from the stack where temps[j] < temps[i] and set result[j] = i - j. Remaining indices have no future warmer day (result = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Increasing vs Decreasing Stack: When to Use Each
Choosing the right stack direction is crucial:
- Monotonic decreasing stack (pop when current > top): answers next greater element and previous greater element queries. Used in daily-temperatures, largest-rectangle, trap-rain-water.
- Monotonic increasing stack (pop when current < top): answers next smaller element and previous smaller element queries. Used in finding the span of stock prices, number of visible people in a queue.
Remember: the element that causes a pop is the answer to the popped element's query — either the next greater or next smaller, depending on which invariant you maintain.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Circular Next Greater Element
Next Greater Element II (LeetCode 503): given a circular array (wrap around), find the next greater element. The trick is to process the array twice by doubling the indices: iterate from 0 to 2n-1, using index % n to wrap around. We push only indices from 0 to n-1 (first pass) so we do not double-count.
Alternatively, process the array in the second pass without pushing new indices — only popping. This handles the circular look-ahead correctly without actually duplicating the array, keeping space O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Stock Span Problem
The Stock Span problem: given daily stock prices, compute the span of each day — the number of consecutive preceding days with price less than or equal to today's price. This is the previous-greater-element problem in disguise: the span is the distance from today back to the nearest day with a strictly higher price.
Use a monotonic decreasing stack. When processing day i, pop all days with price ≤ current. The span is i - stack[-1] if the stack is non-empty, or i + 1 if empty (price is max so far). Then push i.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Monotonic Stack for Visible People in Queue
The Number of Visible People in a Queue problem: people stand in a queue, each with a height. Person i can see person j (j > i) if all people between them are shorter than both. This uses a monotonic decreasing stack.
Process from right to left. Maintain a decreasing stack of heights. For each person, count how many people they can see: pop all shorter people (visible but blocked after), plus 1 if the stack is not empty after (the first taller person is also visible). This gives O(n) overall due to each person being pushed and popped at most once.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n) Guarantee: Why Every Element Is Pushed and Popped At Most Once
The O(n) time guarantee of monotonic stack algorithms comes from a simple amortisation argument: each element is pushed onto the stack exactly once and popped at most once. No element can be pushed or popped more than once. Therefore, the total number of push + pop operations across the entire loop is at most 2n, giving O(n) total work despite the nested while loop appearing to suggest O(n²).
This amortised analysis is important to articulate in interviews. The while loop does not run n times per iteration — it runs only enough to pop elements that were waiting, and those elements are gone forever after being popped.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nRecognising Monotonic Stack Problems
A problem likely needs a monotonic stack if it asks for nearest greater/smaller element, span of prices, visible elements in a line, or histogram-based areas. Look for these keywords and patterns: each element needs the answer from the nearest relevant element in one direction (left or right).
If a brute-force solution scans leftward or rightward from each element (O(n²)), replace that scan with a monotonic stack. The stack 'remembers' candidate answers, discards irrelevant ones, and pops the right answer at exactly the moment it is needed.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()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 increasing or decreasing order by popping elements that violate the invariant before pushing, a decreasing stack answers next/previous greater element while an increasing stack answers next/previous smaller element, and each element is pushed and popped at most once giving O(n) total time — not O(n²). Next up we apply the monotonic stack to find the largest rectangle in a histogram.
Frequently asked questions
Is the “Monotonic Stack: Increasing vs Decreasing” lesson free?
Yes — the full text of “Monotonic Stack: Increasing vs Decreasing” 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: Increasing vs Decreasing”?
Maintain an increasing or decreasing stack to efficiently answer next-greater-element and previous-smaller-element queries 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 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Monotonic Stack: Increasing vs Decreasing” 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.
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