Monotonic stacks and queues are among the most powerful optimization patterns in algorithmic problem solving. They transform O(n²) nested-loop solutions into elegant O(n) single-pass algorithms. They're the secret weapon behind "next greater element," "largest rectangle in histogram," and "sliding window maximum"—problems that appear constantly in FAANG interviews.
But here's the challenge: monotonic stacks aren't intuitive. The first time you see one, it feels like magic. Why does maintaining decreasing order find the next greater element? How does a deque solve sliding window maximum in O(n)? And most importantly, how do you recognize when to use this pattern in an interview?
This comprehensive guide will teach you everything about monotonic stacks and queues: the intuition behind why they work, when to use each variant, complete production-ready templates, and a systematic decision framework that works every time.
A monotonic stack is a stack where elements are always in increasing or decreasing order. As you push elements, you pop any elements that violate the monotonic property.
A monotonic queue (typically implemented with a deque) extends this concept to support both ends, enabling sliding window optimizations.
The fundamental insight: By maintaining monotonicity, you eliminate redundant comparisons and achieve O(n) time complexity for problems that seem to require O(n²).
Array: [3, 1, 4, 1, 5, 9, 2]
Processing 3:
Stack: [3] (empty, just push)
Processing 1:
Stack: [3, 1] (1 < 3, maintains decreasing order)
Processing 4:
Pop 1 (1 < 4, violates decreasing)
Pop 3 (3 < 4, violates decreasing)
Stack: [4]
Processing 1:
Stack: [4, 1] (1 < 4, maintains decreasing)
Processing 5:
Pop 1, Pop 4
Stack: [5]
Processing 9:
Pop 5
Stack: [9]
Processing 2:
Stack: [9, 2] (2 < 9, maintains decreasing)Key observation: Each element is pushed exactly once and popped at most once. Total operations: O(n).
Brute force approach for "next greater element":
# For each element, scan right to find next greater
for i in range(n):
for j in range(i + 1, n):
if arr[j] > arr[i]:
result[i] = arr[j]
break
# Time: O(n²)Monotonic stack approach:
# Maintain decreasing stack, pop when we find greater
stack = []
for i in range(n):
while stack and arr[i] > arr[stack[-1]]:
idx = stack.pop()
result[idx] = arr[i] # arr[i] is next greater for arr[idx]
stack.append(i)
# Time: O(n) - each element pushed/popped onceThe transformation: Instead of asking "what's the next greater element for this position?" we ask "for which previous positions am I the next greater element?" This reversal of perspective enables the O(n) solution.
Monotonic Stack:
Monotonic Queue (Deque):
Question: Do you need to maintain a sliding window?
├─ YES → Monotonic Queue (Deque)
│ Example: Sliding Window Maximum
└─ NO → Monotonic Stack
├─ Finding next greater/smaller → Decreasing/Increasing Stack
└─ Range queries, histogram → Increasing StackProperty: Elements decrease from bottom to top (stack[0] > stack[1] > stack[2] > ...)
Use case: Finding next greater element or previous greater element
Why it works: When you encounter an element larger than the stack top, you've found the "next greater" for all smaller elements in the stack.
Visual:
Array: [2, 1, 5, 6, 2, 3]
Finding next greater element for each position
i=0, val=2: stack=[2]
i=1, val=1: stack=[2,1] (decreasing ✓)
i=2, val=5:
- Pop 1 (5 is next greater for 1)
- Pop 2 (5 is next greater for 2)
- stack=[5]
i=3, val=6:
- Pop 5 (6 is next greater for 5)
- stack=[6]
i=4, val=2: stack=[6,2] (decreasing ✓)
i=5, val=3:
- Pop 2 (3 is next greater for 2)
- stack=[6,3]Property: Elements increase from bottom to top (stack[0] < stack[1] < stack[2] < ...)
Use case: Finding next smaller element or previous smaller element
Why it works: When you encounter an element smaller than the stack top, you've found the "next smaller" for all larger elements in the stack.
Classic problem: Largest Rectangle in Histogram
def next_greater_element(nums):
"""
For each element, find the next greater element to its right.
Time: O(n) - each element pushed and popped at most once
Space: O(n) - stack storage
"""
n = len(nums)
result = [-1] * n # Default: no greater element
stack = [] # Store indices
for i in range(n):
# While current element is greater than stack top
# We found the next greater element for stack top
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
# Remaining elements in stack have no next greater
# (already initialized to -1)
return result
# Example
print(next_greater_element([2, 1, 2, 4, 3]))
# Output: [4, 2, 4, -1, -1]
# Explanation:
# - Next greater for 2 (index 0) is 4
# - Next greater for 1 (index 1) is 2
# - Next greater for 2 (index 2) is 4
# - No next greater for 4 and 3JavaScript:
function nextGreaterElement(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}Java:
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}def next_smaller_element(nums):
"""
For each element, find the next smaller element to its right.
Time: O(n)
Space: O(n)
"""
n = len(nums)
result = [-1] * n
stack = [] # Store indices, maintain increasing order
for i in range(n):
# While current element is smaller than stack top
while stack and nums[i] < nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
# Example
print(next_smaller_element([4, 2, 1, 5, 3]))
# Output: [2, 1, -1, 3, -1]from collections import deque
def sliding_window_maximum(nums, k):
"""
Find maximum in each sliding window of size k.
Time: O(n) - each element added and removed at most once
Space: O(k) - deque stores at most k elements
"""
result = []
dq = deque() # Store indices, maintain decreasing order of values
for i in range(len(nums)):
# Remove elements outside current window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove elements smaller than current (they'll never be max)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
# Add to result once we have a full window
if i >= k - 1:
result.append(nums[dq[0]]) # Front is always maximum
return result
# Example
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [3, 3, 5, 5, 6, 7]JavaScript:
function slidingWindowMaximum(nums, k) {
const result = [];
const dq = []; // Deque (use array with shift/pop)
for (let i = 0; i < nums.length; i++) {
// Remove out-of-window elements
while (dq.length > 0 && dq[0] < i - k + 1) {
dq.shift();
}
// Maintain decreasing order
while (dq.length > 0 && nums[i] > nums[dq[dq.length - 1]]) {
dq.pop();
}
dq.push(i);
if (i >= k - 1) {
result.push(nums[dq[0]]);
}
}
return result;
}Java:
public int[] slidingWindowMaximum(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// Remove out-of-window
while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
dq.pollFirst();
}
// Maintain decreasing order
while (!dq.isEmpty() && nums[i] > nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[dq.peekFirst()];
}
}
return result;
}1. Next Greater Element I (LeetCode #496)
def nextGreaterElement(nums1, nums2):
"""
Find next greater element for nums1 elements in nums2.
Time: O(n + m)
Space: O(n)
"""
# Build next greater map for nums2
next_greater = {}
stack = []
for num in nums2:
while stack and num > stack[-1]:
next_greater[stack.pop()] = num
stack.append(num)
# Map nums1 to their next greater
return [next_greater.get(num, -1) for num in nums1]2. Daily Temperatures (LeetCode #739)
def dailyTemperatures(temperatures):
"""
For each day, find how many days until warmer temperature.
Time: O(n)
Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # Store indices
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
idx = stack.pop()
result[idx] = i - idx # Days difference
stack.append(i)
return result
# Example
print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]Why monotonic stack works: We maintain a decreasing stack of temperatures. When we find a warmer day, we pop all colder days and record the distance.
See detailed guide: Monotonic Decreasing Stack Template
This is the canonical monotonic increasing stack problem.
def largestRectangleArea(heights):
"""
Find largest rectangle in histogram.
Time: O(n)
Space: O(n)
"""
stack = [] # Store indices, maintain increasing heights
max_area = 0
heights = [0] + heights + [0] # Add sentinels
for i in range(len(heights)):
# When we find a shorter bar, calculate areas
while stack and heights[i] < heights[stack[-1]]:
h_idx = stack.pop()
height = heights[h_idx]
width = i - stack[-1] - 1 # Distance between boundaries
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Example
print(largestRectangleArea([2, 1, 5, 6, 2, 3]))
# Output: 10 (rectangle with height 5, width 2)Why it works:
Key insight: For a bar at index i with height h, the maximum rectangle is:
hSee detailed guide: Monotonic Increasing Stack Template
from collections import deque
def maxSlidingWindow(nums, k):
"""
Find maximum in each sliding window of size k.
Approach: Monotonic decreasing deque
- Front always contains index of maximum in current window
- Remove elements outside window from front
- Remove smaller elements from back (they'll never be max)
Time: O(n)
Space: O(k)
"""
result = []
dq = deque()
for i in range(len(nums)):
# Remove out-of-window elements
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order (remove smaller elements)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
# Add maximum of current window
if i >= k - 1:
result.append(nums[dq[0]])
return resultWhy deque (not stack)?
Why not priority queue?
See detailed guide: Monotonic Queue Template
class StockSpanner:
"""
Calculate stock price span: number of consecutive days
with price <= today's price.
Example: [100, 80, 60, 70, 60, 75, 85]
Spans: [1, 1, 1, 2, 1, 4, 6]
"""
def __init__(self):
self.stack = [] # (price, span)
def next(self, price):
span = 1
# Pop all smaller or equal prices
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
# Usage
spanner = StockSpanner()
print(spanner.next(100)) # 1
print(spanner.next(80)) # 1
print(spanner.next(60)) # 1
print(spanner.next(70)) # 2
print(spanner.next(60)) # 1
print(spanner.next(75)) # 4
print(spanner.next(85)) # 6Why monotonic stack works: We maintain a decreasing stack. When a new price arrives, we pop all smaller prices and accumulate their spans.
Finding next/previous greater/smaller element
Histogram or rectangle problems
Range queries with min/max
Can make greedy decisions based on monotonicity
Sliding window maximum/minimum
Need to remove from both ends
Need to track all elements (not just extremes)
Order doesn't matter
Need exact values, not just comparisons
Problem requires O(1) space
❌ Wrong:
# Want next GREATER, but using INCREASING stack
while stack and nums[i] < nums[stack[-1]]: # Wrong comparison
stack.pop()✅ Correct:
# Next GREATER needs DECREASING stack
while stack and nums[i] > nums[stack[-1]]: # Correct
idx = stack.pop()
result[idx] = nums[i]Rule:
See guide: Next Greater Element Mistakes
❌ Wrong:
stack.append(nums[i]) # Storing value
# Later: can't calculate distance or access original array✅ Correct:
stack.append(i) # Storing index
# Later: can calculate i - stack[-1], or access nums[stack[-1]]When to store indices:
When values are sufficient:
See guide: Indices vs Values
❌ Wrong:
# Using strict inequality for contribution technique
while stack and nums[i] > nums[stack[-1]]: # Counts duplicates twice
stack.pop()✅ Correct:
# Use >= on one side to avoid double-counting
while stack and nums[i] >= nums[stack[-1]]: # Correct
stack.pop()See guide: Handling Duplicates
❌ Wrong:
# Using stack for sliding window maximum
# Can't remove from front efficiently!✅ Correct:
# Use deque for sliding window
from collections import deque
dq = deque()For problems requiring both "next smaller to left" and "next smaller to right":
def find_boundaries(nums):
"""
Find next smaller element on both sides.
Used in: Largest Rectangle, Sum of Subarray Minimums
"""
n = len(nums)
left = [-1] * n # Next smaller to left
right = [n] * n # Next smaller to right
stack = []
# Left pass
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
# Right pass
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[i] < nums[stack[-1]]:
stack.pop()
right[i] = stack[-1] if stack else n
stack.append(i)
return left, rightCalculate sum/count by determining each element's contribution:
def sumSubarrayMins(arr):
"""
LeetCode #907: Sum of Subarray Minimums
For each element, count subarrays where it's the minimum,
then multiply by the element value.
Time: O(n)
"""
n = len(arr)
left, right = find_boundaries(arr)
result = 0
MOD = 10**9 + 7
for i in range(n):
# Count of subarrays where arr[i] is minimum
left_count = i - left[i] # Elements to the left
right_count = right[i] - i # Elements to the right
count = left_count * right_count
# Contribution of arr[i]
result = (result + arr[i] * count) % MOD
return resultSee detailed guide: Contribution Technique
The amortized analysis:
Each element is:
Total operations: 2n = O(n)
Proof by example:
Array: [3, 1, 4, 1, 5]
Element 3: Push (1 op)
Element 1: Push (1 op)
Element 4: Pop 1, Pop 3, Push 4 (3 ops total)
Element 1: Push (1 op)
Element 5: Pop 1, Pop 4, Push 5 (3 ops total)
Total: 9 operations for 5 elements
Each element: 1 push + at most 1 pop = 2 ops max
Total: O(n)See detailed proof: Why Stack Beats Brute Force
Worst case: all elements in increasing (or decreasing) order
A: Each element enters the stack exactly once (one push). It can leave the stack at most once (one pop). Even if the while loop runs multiple times, each iteration pops a different element. Total operations across all elements: O(n).
A:
A:
> or <)>= on one side, > on the other to avoid double-countingA: Yes! Maximal Rectangle (#85) uses monotonic stack on each row. Convert 2D problem to multiple 1D histogram problems.
A:
Monotonic stacks and queues are powerful optimization patterns that transform O(n²) solutions into O(n) elegance. They're essential for FAANG interviews and appear in dozens of LeetCode problems.
Key principles:
The templates:
# Next Greater (Decreasing Stack)
while stack and nums[i] > nums[stack[-1]]:
result[stack.pop()] = nums[i]
# Next Smaller (Increasing Stack)
while stack and nums[i] < nums[stack[-1]]:
result[stack.pop()] = nums[i]
# Sliding Window Max (Decreasing Deque)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()When to use:
Master these patterns, and you'll solve an entire class of problems with confidence. For deep dives into specific variants, see:
Next time you see "next greater element" or "largest rectangle," reach for the monotonic stack. Your interview performance will thank you.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free