A stack that stays sorted. Sounds simple, but it's the key to solving "next greater element," "largest rectangle in histogram," and sliding window maximum โ all in O(n) time. Once you internalize this pattern, a whole category of problems opens up.
IntermediateA monotonic stack is a stack (last-in, first-out data structure) where elements are always in sorted order โ either always increasing from bottom to top (monotonically increasing) or always decreasing (monotonically decreasing). You maintain this property by popping elements that violate it before pushing a new one.
The word "monotonic" comes from mathematics โ a monotonic function is one that only goes up or only goes down, never switching direction. A monotonic stack enforces the same constraint: reading from bottom to top, values only go one way.
Here's an analogy. Imagine a line of people ordered by height, tallest at the back. When a new person arrives, anyone shorter than them leaves the line (they were "blocked" by the newcomer). The line always maintains its height ordering. That's a monotonically decreasing stack (tallest at bottom, shortest at top). What's interesting is what happens to the people who leave โ that's where the problem-specific logic lives.
The magic of monotonic stacks: each element is pushed exactly once and popped at most once across the entire algorithm. Even though a single push might trigger multiple pops, the total work across all operations is O(n). This is called amortized analysis โ the average cost per operation is O(1), even if individual operations occasionally cost more.
This is the most confusing part for beginners, because different sources use different conventions. Let's be precise:
Mnemonic: the stack "points toward" what you're looking for. An increasing stack has small things on top, so it helps you find the next smaller thing. A decreasing stack has large things on top, helping you find the next greater thing. If this feels backward, just trace through a small example โ it clicks after doing one or two.
A regular stack has no ordering constraint โ you push and pop whatever you want. A monotonic stack enforces an invariant (a property that's always true): before pushing a new element, you pop everything that breaks the monotonic order. What you do with those popped elements โ compute an area, record a "next greater" answer, update a count โ is where the problem-specific logic lives.
A monotonic deque (double-ended queue) is the same idea but with an extra feature: elements can be removed from the front too. This is essential for sliding window problems where you need to remove elements that have fallen outside the window.
A deque (pronounced "deck") supports O(1) insertion and removal at both ends. Python's collections.deque and JavaScript's array (with shift/push) provide this. For a sliding window maximum, maintain a decreasing deque of indices โ the front always holds the index of the current window's maximum.
Problem: given array [2, 1, 2, 4, 3], find the next greater element for each position. If none exists, output -1.
Approach: Walk right to left. Maintain a decreasing stack (bottom = largest, top = smallest). For each element, pop everything โค it (they can't be the "next greater" for anything further left). If the stack isn't empty after popping, the top is the answer. Push the current element.
Trace:
Result: [4, 2, 4, -1, -1].
Why right to left? Because we need to know what's to the right of each element. By going right to left, we build up knowledge of the right side before we need it. The stack acts as a "candidates" list โ elements that could potentially be the next greater for elements we haven't processed yet.
Alternative: left to right. You can also solve NGE by scanning left to right. Push indices onto the stack. When you encounter a value larger than the stack top's value, that value IS the next greater for the stack top โ pop it and record the answer. Elements remaining on the stack at the end have no next greater element. Both approaches work; the left-to-right version is sometimes easier for "online" problems where elements arrive one at a time.
Given heights [2, 1, 5, 6, 2, 3], find the area of the largest rectangle that fits under the bars.
For each bar, the maximum rectangle using that bar's height extends left until it hits a shorter bar, and right until it hits a shorter bar. So we need each bar's left boundary (nearest shorter bar to the left) and right boundary (nearest shorter bar to the right).
A monotonically increasing stack (bottom = smallest) handles this. Walk left to right, pushing indices:
The sentinel trick: append a bar of height 0 at the end. This forces all remaining bars off the stack, so we don't need special handling for bars that extend to the right edge.
Trace with [2, 1, 5, 6, 2, 3, 0] (0 is sentinel):
Maximum area: 10 (the 5-high rectangle spanning columns 2-3).
Given array [1, 3, -1, -3, 5, 3, 6, 7] and window size k=3, find the maximum in each window of size k.
Maintain a decreasing deque of indices (front = largest value, back = smallest). For each new element:
Each element enters and exits the deque exactly once โ O(n) total, regardless of window size.
For each element arr[i], count how many subarrays have arr[i] as their minimum. If arr[i] is the minimum of S subarrays, it contributes arr[i] ร S to the total sum.
To find S for each i, we need:
Then S = left[i] ร right[i], and the total sum = ฮฃ arr[i] ร left[i] ร right[i].
nums[stack[-1]]. Storing values directly loses positional information.
<= vs. < in the pop condition matters a lot. For "next strictly greater" use <= to pop equal elements. For "next greater or equal," use < to keep equal elements. In "Sum of Subarray Minimums," using strict on one side and non-strict on the other prevents double-counting subarrays where the minimum appears at multiple positions. Get this wrong and your answer will be off.
top at position i: if the stack is empty after the pop, the left boundary is -1 (the bar extends all the way left). Width = i - stack[-1] - 1 if stack is non-empty, or i if stack is empty. Getting this wrong (using i - top or forgetting the empty-stack case) gives incorrect areas.
| Problem | Time | Space | Approach |
|---|---|---|---|
| Next Greater Element | O(n) | O(n) | Decreasing stack, RโL or LโR |
| Next Smaller Element | O(n) | O(n) | Increasing stack, RโL or LโR |
| Previous Greater Element | O(n) | O(n) | Decreasing stack, LโR |
| Previous Smaller Element | O(n) | O(n) | Increasing stack, LโR |
| Largest Rectangle Histogram | O(n) | O(n) | Increasing stack of indices |
| Maximal Rectangle (2D) | O(rows ร cols) | O(cols) | Histogram per row |
| Sliding Window Maximum | O(n) | O(k) | Decreasing deque |
| Stock Span | O(n) | O(n) | Decreasing stack |
| Trapping Rain Water | O(n) | O(n) | Stack or two pointers (O(1) space) |
| Sum of Subarray Minimums | O(n) | O(n) | Left/right boundaries via stack |
The key insight across all of these: every element is pushed once and popped at most once. Total pushes + total pops โค 2n. So even though the inner while loop might pop several elements on a single iteration, the total work summed over ALL iterations is O(n). This amortized O(n) is what makes monotonic stacks so efficient.
def next_greater(nums):
"""For each element, find the first strictly greater element to its right.
Returns -1 if none exists.
Uses a decreasing stack (bottom=largest, top=smallest).
Scan right to left: for each element, pop everything <= it
(they're blocked by the current element), then the top is the answer.
Time: O(n) amortized. Space: O(n)."""
n = len(nums)
result = [-1] * n
stack = [] # stores indices; values at those indices are in decreasing order
for i in range(n - 1, -1, -1):
# Pop elements that aren't strictly greater than current.
# They can never be the NGE for anything further left either,
# because the current element is >= them and closer.
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
# If stack isn't empty, top is the next greater element
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
# next_greater([2, 1, 2, 4, 3]) โ [4, 2, 4, -1, -1]
# next_greater([4, 3, 2, 1]) โ [-1, -1, -1, -1]
# next_greater([1, 2, 3, 4]) โ [2, 3, 4, -1]
def next_greater_lr(nums):
"""Same result as above, but scanning left to right.
When we find a value greater than the stack top,
that value IS the next greater for the top.
This version is better for "online" problems
where elements arrive one at a time."""
n = len(nums)
result = [-1] * n
stack = [] # indices of elements waiting for their NGE
for i in range(n):
# Current element is the answer for everything on the stack
# that it's greater than
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
# Elements remaining on stack have no next greater element
# (result already initialized to -1)
return result
function nextGreater(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = []; // indices, maintaining decreasing order of values
for (let i = n - 1; i >= 0; i--) {
// Pop elements that aren't strictly greater
while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
stack.pop();
}
if (stack.length) {
result[i] = nums[stack[stack.length - 1]];
}
stack.push(i);
}
return result;
}
def next_greater_circular(nums):
"""Next greater element where the array wraps around.
[1, 2, 1] โ [2, -1, 2] (the last 1's NGE is the first 2).
Trick: iterate through the array TWICE (indices 0 to 2n-1)
but only write results for the first n elements.
Use i % n to wrap indices. This handles the circular nature."""
n = len(nums)
result = [-1] * n
stack = []
# Process 2n elements: the array "repeated twice"
for i in range(2 * n - 1, -1, -1):
idx = i % n
while stack and nums[stack[-1]] <= nums[idx]:
stack.pop()
if stack and i < n: # only record for first pass
result[idx] = nums[stack[-1]]
stack.append(idx)
return result
# next_greater_circular([1, 2, 1]) โ [2, -1, 2]
function nextGreaterCircular(nums) {
// Next greater element in a circular array
// [1, 2, 1] โ [2, -1, 2] (last 1 wraps around to first 2)
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
// Process 2n elements: the array conceptually repeated twice
for (let i = 2 * n - 1; i >= 0; i--) {
const idx = i % n;
while (stack.length && nums[stack[stack.length - 1]] <= nums[idx]) {
stack.pop();
}
if (stack.length && i < n) {
result[idx] = nums[stack[stack.length - 1]];
}
stack.push(idx);
}
return result;
}
def largest_rectangle(heights):
"""Find the largest rectangular area in a histogram.
Maintain a monotonically increasing stack of indices.
When we hit a bar shorter than the stack top, the top bar's
maximum rectangle is determined: its right boundary is the
current index, its left boundary is the new stack top.
The sentinel (height 0 at the end) forces all remaining
bars off the stack.
Time: O(n), Space: O(n)."""
stack = [] # indices of bars in increasing height order
max_area = 0
heights.append(0) # sentinel: forces processing of all bars
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# Width: from current position back to the bar
# after the new stack top.
# If stack is empty, this bar extended all the way
# to the left edge โ width = i.
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
heights.pop() # remove sentinel to not mutate input
return max_area
# largest_rectangle([2, 1, 5, 6, 2, 3]) โ 10
# (the 5ร2 rectangle spanning bars with heights 5 and 6)
function largestRectangle(heights) {
const stack = [];
let maxArea = 0;
heights.push(0); // sentinel
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
const height = heights[stack.pop()];
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
heights.pop(); // remove sentinel
return maxArea;
}
// largestRectangle([2, 1, 5, 6, 2, 3]) โ 10
def maximal_rectangle(matrix):
"""Find the largest rectangle containing only 1s in a binary matrix.
Key insight: treat each row as the base of a histogram.
For each row, compute the histogram heights (consecutive 1s
above each cell), then apply largest_rectangle.
Time: O(rows ร cols), Space: O(cols)."""
if not matrix or not matrix[0]:
return 0
cols = len(matrix[0])
heights = [0] * cols
max_area = 0
for row in matrix:
# Build histogram: if current cell is 1, add to height.
# If 0, reset height to 0 (can't continue the bar).
for j in range(cols):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, largest_rectangle(heights[:]))
return max_area
# matrix = [
# ["1","0","1","0","0"],
# ["1","0","1","1","1"],
# ["1","1","1","1","1"],
# ["1","0","0","1","0"]
# ]
# maximal_rectangle(matrix) โ 6 (the 3ร2 block in rows 2-3, cols 2-3)
from collections import deque
def max_sliding_window(nums, k):
"""Find the maximum value in each sliding window of size k.
Maintain a decreasing deque of indices.
Front of deque = index of current window's maximum.
For each new element:
1. Remove from front: indices outside the window
2. Remove from back: indices with values <= new element
(they can never be the max while new element is in window)
3. Push new index to back
4. Record answer from front (once window is full)
Time: O(n), Space: O(k)."""
dq = deque() # indices, values are in decreasing order
result = []
for i, num in enumerate(nums):
# Evict expired elements (outside window)
while dq and dq[0] <= i - k:
dq.popleft()
# Evict elements smaller than current from back.
# They're now useless: current is both newer AND larger.
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
# Window is full (we've seen at least k elements)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# max_sliding_window([1,3,-1,-3,5,3,6,7], 3)
# โ [3, 3, 5, 5, 6, 7]
function maxSlidingWindow(nums, k) {
// Monotonic deque: front = index of window max, decreasing order
const deque = []; // indices
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove expired indices from front
while (deque.length && deque[0] <= i - k) {
deque.shift();
}
// Remove smaller values from back (useless while current exists)
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
// Window is full
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
// maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) โ [3,3,5,5,6,7]
def sum_subarray_mins(arr):
"""Sum of minimum values across all contiguous subarrays.
For each element arr[i], count the number of subarrays where
arr[i] is the minimum. Its contribution = arr[i] ร count.
count = left[i] ร right[i], where:
- left[i] = distance to previous STRICTLY smaller element
- right[i] = distance to next SMALLER OR EQUAL element
The asymmetry (strict vs non-strict) prevents double-counting
when there are duplicate values.
Time: O(n), Space: O(n)."""
MOD = 10**9 + 7
n = len(arr)
# Previous smaller (strict): increasing stack, left to right
left = [0] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
# Next smaller or equal: increasing stack, right to left
right = [0] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
# Sum contributions
total = 0
for i in range(n):
total = (total + arr[i] * left[i] * right[i]) % MOD
return total
# sum_subarray_mins([3, 1, 2, 4]) โ 17
# Subarrays: [3]=3, [1]=1, [2]=2, [4]=4, [3,1]=1, [1,2]=1,
# [2,4]=2, [3,1,2]=1, [1,2,4]=1, [3,1,2,4]=1
# Sum: 3+1+2+4+1+1+2+1+1+1 = 17
def trap_rain_water(height):
"""Calculate trapped rainwater using a monotonic stack.
The stack-based approach computes water layer by layer
(horizontal slices), unlike the two-pointer approach which
computes column by column (vertical slices).
Maintain a decreasing stack. When we find a bar taller than
the top, water is trapped between the current bar and the
bar below the top. The top itself is the "floor" of the water.
Time: O(n), Space: O(n)."""
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = height[stack.pop()] # floor of the water
if not stack:
break # no left wall
# Water level is min of left wall and right wall (current)
bounded_height = min(height[stack[-1]], h) - bottom
width = i - stack[-1] - 1
water += bounded_height * width
stack.append(i)
return water
# trap_rain_water([0,1,0,2,1,0,1,3,2,1,2,1]) โ 6
Imagine you're building a weather monitoring system. For each day's temperature reading, you want to know: "how many days until a warmer day?" This is exactly the "daily temperatures" problem โ and it's a direct application of monotonic stacks.
from datetime import datetime, timedelta
def temperature_alerts(readings):
"""Given a list of (date, temperature) readings, compute for each day:
- Days until a warmer day (0 if none)
- Whether this is a new high (no previous day was warmer)
Uses a monotonic stack to find the next warmer day in O(n).
In production, this would run on a streaming data pipeline
(Kafka/Flink) โ the left-to-right variant handles one reading
at a time without needing the full dataset upfront."""
n = len(readings)
days_until_warmer = [0] * n
stack = [] # indices of days waiting for a warmer day
for i, (date, temp) in enumerate(readings):
# Current day is warmer than everything on the stack
# that has a lower temperature
while stack and readings[stack[-1]][1] < temp:
waiting_idx = stack.pop()
days_until_warmer[waiting_idx] = i - waiting_idx
stack.append(i)
# Print alerts
print(f"{'Date':<12} {'Temp':>6} {'Days to Warmer':>16} {'Note'}")
print("-" * 50)
for i, (date, temp) in enumerate(readings):
note = ""
if days_until_warmer[i] == 0:
# Check if it's a new all-time high
if all(t <= temp for _, t in readings[:i]):
note = "๐ฅ New high!"
else:
note = "No warmer day in range"
formatted_date = date.strftime("%Y-%m-%d")
print(f"{formatted_date:<12} {temp:>5.1f}ยฐ {days_until_warmer[i]:>15}d {note}")
# Simulated 10-day weather data
dates = [datetime(2026, 3, 1) + timedelta(days=i) for i in range(10)]
temps = [73, 74, 75, 71, 69, 72, 76, 73, 74, 78]
readings = list(zip(dates, temps))
temperature_alerts(readings)
# 2026-03-01 73.0ยฐ 1d
# 2026-03-02 74.0ยฐ 1d
# 2026-03-03 75.0ยฐ 4d
# 2026-03-04 71.0ยฐ 2d
# 2026-03-05 69.0ยฐ 1d
# 2026-03-06 72.0ยฐ 1d
# 2026-03-07 76.0ยฐ 3d
# 2026-03-08 73.0ยฐ 1d
# 2026-03-09 74.0ยฐ 1d
# 2026-03-10 78.0ยฐ 0d ๐ฅ New high!
The same pattern appears in stock trading (finding the next day a stock exceeds a price), server monitoring (finding the next time CPU load exceeds a threshold), and event processing systems. The left-to-right variant is particularly useful in streaming contexts where data arrives one element at a time.
Financial platforms compute the stock span: for each day, how many consecutive previous days had a price less than or equal to today's price? This is used in technical analysis indicators. A decreasing monotonic stack solves it in O(1) amortized per day, even in a streaming context where prices arrive one at a time.
class StockSpanner {
constructor() {
// Stack of [price, span] pairs in decreasing price order
this.stack = [];
}
next(price) {
let span = 1;
// Pop all days with price <= today's price
// Their span gets absorbed into today's span
while (this.stack.length &&
this.stack[this.stack.length - 1][0] <= price) {
span += this.stack.pop()[1];
}
this.stack.push([price, span]);
return span;
}
}
// Simulated daily stock prices
const spanner = new StockSpanner();
const prices = [100, 80, 60, 70, 60, 75, 85];
const spans = prices.map(p => spanner.next(p));
// spans: [1, 1, 1, 2, 1, 4, 6]
// Day with price 85: the previous 5 days (75,60,70,60,80) + itself = span 6Monitoring systems like Prometheus and Datadog track metrics over sliding windows. "What's the maximum CPU usage in the last 5 minutes?" is a sliding window maximum problem. A monotonic deque gives O(1) amortized per data point, handling millions of metrics per second without falling behind.
In computer vision, finding the largest axis-aligned rectangle that fits inside a binary shape (white pixels = valid, black = invalid) reduces to the "maximal rectangle in a binary matrix" problem โ which itself reduces to "largest rectangle in histogram" applied row by row. This is used in document scanning (finding the largest clean area), object detection bounding boxes, and UI layout engines.
i - stack[-1] (or i + 1 if stack is empty). This also appears in "number of visible people in a queue."
| # | Problem | Difficulty | Key Concept |
|---|---|---|---|
| 496 | Next Greater Element I | Easy | Monotonic stack basics |
| 503 | Next Greater Element II | Medium | Circular array + stack |
| 84 | Largest Rectangle in Histogram | Hard | Increasing stack |
| 85 | Maximal Rectangle | Hard | Histogram per row |
| 239 | Sliding Window Maximum | Hard | Monotonic deque |
| 42 | Trapping Rain Water | Hard | Stack or two pointers |
| 907 | Sum of Subarray Minimums | Medium | Contribution counting |
| 901 | Online Stock Span | Medium | Previous greater element |
| 739 | Daily Temperatures | Medium | Next warmer day |
| 1944 | Number of Visible People in a Queue | Hard | Decreasing stack |