Monotonic Stack & Monotonic Deque
A monotonic stack is an ordinary stack with one discipline imposed on it: reading from bottom to top, the values it holds are always sorted (increasing, or decreasing, strictly or not). Before pushing a new element you pop every element that would break the order. A monotonic deque is the same idea on a deque, so that elements can also expire from the other end.
That one rule turns a surprising number of quadratic problems into linear ones: the next greater element of every position, the span of every stock price, the largest rectangle under a histogram, the sum of the minimums of all subarrays, the smallest number after deleting digits, and the maximum of every window of size . The Advanced Data Structures page has a short section with two examples; this lesson goes much deeper — it proves why the technique is linear, shows exactly how to handle duplicates without double counting, and builds the full family of problems on one lemma.
Why this exists
Many questions about an array have the form "for each position, find the nearest position to the left (or right) whose value is smaller (or greater)". Asked naïvely, each position scans outward until it finds the answer, and an adversarial input such as a sorted array makes every scan long: total. Yet the answers are highly structured. If and , then can never be the "previous greater element" of anything to the right of , because is both closer and at least as large. Elements that are dominated in this way can be thrown away forever. What remains after discarding every dominated element is a sorted sequence, and the right container for it is a stack.
The problem has a name in the parallel-algorithms literature: all nearest smaller values (ANSV). Berkman, Schieber and Vishkin studied it in 1993 as a building block for parallel algorithms (merging, triangulating monotone polygons, building Cartesian trees, parenthesis matching), and gave an optimal -time parallel algorithm on a CRCW PRAM. The sequential stack algorithm was folklore well before that; it is the same algorithm that builds a Cartesian tree in linear time, which Gabow, Bentley and Tarjan used in 1984 to reduce range-minimum queries to lowest common ancestors.
In interviews the monotonic stack is one of the highest-yield patterns there is: a handful of problems (daily temperatures, largest rectangle, trapping rain water, sum of subarray minimums, remove digits, sliding window maximum) appear constantly, and every one of them is the same lemma wearing a different coat. In production the same structure computes stock spans, rolling maxima for monitoring alerts, and is the inner loop of several data-structure constructions.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "next greater / next smaller element", "first element to the right that is…" | Monotonic stack scanning in one direction |
| "previous greater / smaller", "nearest … to the left" | Monotonic stack; the answer is the stack top after popping |
| "how many consecutive days before…", "span", "days until warmer" | Previous/next greater with distances (store indices) |
| "largest rectangle", "maximal area in histogram / binary matrix" | Previous and next smaller per bar, or the one-pass stack with a 0 sentinel |
| "sum over all subarrays of min / max", "sum of subarray ranges" | Contribution technique: each element times the number of subarrays where it is the extreme |
| "remove digits / characters to make the result smallest / largest", "smallest subsequence" | Greedy monotonic stack with a removal budget |
| "trapping rain water" | Monotonic decreasing stack (or two pointers) |
| "pattern with " (132) | Decreasing stack scanned from the right, tracking the best "2" |
| "fleets", "cars catch up", "collisions in one direction" | Sort by position, then a monotonic stack of arrival times |
| "maximum / minimum of every window of size " | Monotonic deque of indices |
| "shortest subarray with sum at least " with negatives | Prefix sums + monotonic increasing deque |
| "dp[i] depends on max/min of dp over the last positions" | Monotonic deque over DP values |
| "longest subarray where max − min ≤ limit" | Two monotonic deques (one for max, one for min) + sliding window |
The literal words to listen for: next, previous, nearest, span, until, window, all subarrays, rectangle.
Intuition & first principles
Domination
Scan left to right looking for each element's next greater element (NGE): the first index to its right with a strictly larger value. Keep a stack of indices that have not yet found their answer. When a new value arrives at index :
- every index on the stack with has just found its answer, because is the first index after whose value exceeds (anything between them was smaller, or would have been popped earlier);
- after popping them, the stack top (if any) has value , so is not its answer, and neither is it for anything below.
So the stack of "still waiting" indices always has non-increasing values from bottom to top. That is the monotonic invariant, and it is not imposed artificially — it is forced by the question. A waiting element that was smaller than one above it would already have been answered.
The key lemma: each index is pushed once and popped at most once
Lemma. In any monotonic-stack scan over elements in which each element is pushed exactly once, the total number of pop operations is at most , so the total work is even though the inner while loop can pop many elements at a single step.
Proof. Every pop removes an element that was pushed earlier, and an element once popped is never pushed again. Hence #pops ≤ #pushes = . Each iteration of the inner loop does one pop plus work, and each outer iteration does one push plus one failed loop test. Total: .
The same argument in potential-function form: let be the stack size. A push costs 1 and raises by 1 (amortized cost 2); a pop costs 1 and lowers by 1 (amortized cost 0). Every step therefore has amortized cost , and always. See Complexity Analysis.
What the pops mean. The lemma is not only about cost. When pops , it is because is 's next greater element (for a decreasing stack) or next smaller element (for an increasing stack). And when the popping stops, the remaining top is 's previous greater-or-equal (or smaller-or-equal) element. One scan therefore yields two answers per index: the right neighbour from the pop event and the left neighbour from the post-pop top.
The four variants
| Want, for each index | Scan | Stack (bottom → top) | Pop while | Answer recorded |
|---|---|---|---|---|
| Next greater to the right | left → right | decreasing | a[top] < a[i] | for popped top: i |
| Next smaller to the right | left → right | increasing | a[top] > a[i] | for popped top: i |
| Previous greater to the left | left → right | decreasing | a[top] <= a[i] | for i: the top after popping |
| Previous smaller to the left | left → right | increasing | a[top] >= a[i] | for i: the top after popping |
You can equally compute "next" answers by scanning right to left and reading the top after popping. Choose whichever makes the code read naturally.
Strict versus non-strict, and duplicates
With distinct values, < and <= in the pop condition give the same result. With duplicates they do not, and getting this right is the whole difference between a correct and an incorrect solution in the contribution problems.
- Pop while
a[top] < a[i](strict): equal elements stay on the stack. A poppedtoplearns its next strictly greater element;ilearns its previous greater-or-equal element. - Pop while
a[top] <= a[i](non-strict): equal elements are popped. A poppedtoplearns its next greater-or-equal element;ilearns its previous strictly greater element.
Rule of thumb: the pop condition decides strictness for the right side; the left side gets the complement. When you need both sides from separate passes, decide each side's strictness explicitly and write it in a comment.
Mechanics
Next greater element
flowchart TD
START["i = 0, stack = empty, ans = all -1"] --> LOOP{"i < n?"}
LOOP -->|"no"| DONE["indices left on stack have no NGE: ans stays -1"]
LOOP -->|"yes"| CHECK{"stack non-empty and<br/>a[top] < a[i]?"}
CHECK -->|"yes"| POP["j = pop()<br/>ans[j] = a[i]"]
POP --> CHECK
CHECK -->|"no"| PUSH["push i"]
PUSH --> INC["i = i + 1"]
INC --> LOOP
Trace: next greater element on [2, 1, 2, 4, 3] (computed by script; the stack holds indices, values in parentheses):
| i | a[i] | Pops (index → its NGE) | Stack after (indices) | Stack values | Result so far |
|---|---|---|---|---|---|
| 0 | 2 | none | [0] | [2] | [-1, -1, -1, -1, -1] |
| 1 | 1 | none | [0, 1] | [2, 1] | [-1, -1, -1, -1, -1] |
| 2 | 2 | 1 (value 1) → 2 | [0, 2] | [2, 2] | [-1, 2, -1, -1, -1] |
| 3 | 4 | 2 (value 2) → 4, 0 (value 2) → 4 | [3] | [4] | [4, 2, 4, -1, -1] |
| 4 | 3 | none | [3, 4] | [4, 3] | [4, 2, 4, -1, -1] |
Final answer [4, 2, 4, -1, -1]. At the strict condition matters: the value 2 at index 0 is not popped by the equal value 2 at index 2, because 2 is not a strictly greater element. Both 2s wait together and are released by the 4. Five pushes, three pops: within the lemma's bound of pops.
Largest rectangle in a histogram
Bars of width 1 with heights ; find the largest axis-aligned rectangle under the skyline.
Structural fact. A maximal rectangle has some bar that is its shortest bar (its height equals ), and it extends left and right as far as possible while every bar is at least : from just after the previous strictly-smaller bar to just before the next smaller bar . So
One-pass algorithm. Keep an increasing stack of indices. Append a sentinel bar of height 0 at index . For each , while h[top] >= h[i], pop top: its right boundary is (the first bar to its right that is no taller; the proof explains why popping on equality is safe), its left boundary is the new top (or −1 if the stack is empty), and its candidate area is h[top] * (i - left - 1). Then push . The sentinel forces every remaining bar to be popped at the end.
flowchart LR
A["read bar i (height h, sentinel 0 at i = n)"] --> B{"h[top] >= h?"}
B -->|"yes"| C["top = pop()<br/>left = new top or -1<br/>area = h[top] * (i - left - 1)"]
C --> D["best = max(best, area)"]
D --> B
B -->|"no or empty"| E["push i"]
E --> A
Trace: largest rectangle on [2, 1, 5, 6, 2, 3] with the sentinel 0 appended at index 6 (computed by script):
| i | h[i] | Pops with area computed | Stack after (indices) | Best |
|---|---|---|---|---|
| 0 | 2 | none | [0] | 0 |
| 1 | 1 | pop 0 (h = 2): width 1 − (−1) − 1 = 1, area 2 | [1] | 2 |
| 2 | 5 | none | [1, 2] | 2 |
| 3 | 6 | none | [1, 2, 3] | 2 |
| 4 | 2 | pop 3 (h = 6): width 4 − 2 − 1 = 1, area 6; pop 2 (h = 5): width 4 − 1 − 1 = 2, area 10 | [1, 4] | 10 |
| 5 | 3 | none | [1, 4, 5] | 10 |
| 6 | 0 (sentinel) | pop 5 (h = 3): width 6 − 4 − 1 = 1, area 3; pop 4 (h = 2): width 6 − 1 − 1 = 4, area 8; pop 1 (h = 1): width 6 − (−1) − 1 = 6, area 6 | [6] | 10 |
The answer 10 is the rectangle of height 5 spanning bars 2 and 3. Notice how bar 4 (height 2) popped bar 2 and computed width 2 because its left boundary is bar 1 (height 1), the first shorter bar to the left. Without the sentinel, bars 1, 4 and 5 would never be popped and the area-8 rectangle of height 2 would be missed (here it would not change the answer, but on [1, 2, 3, 4, 5] the answer 9 is found only by the final flush).
Maximal rectangle in a binary matrix. Process rows top to bottom, maintaining heights[c] = number of consecutive 1s ending at the current row in column (reset to 0 on a 0). Each row's heights is a histogram; run the algorithm above on it and take the maximum over rows. Time .
Contribution technique: sum of subarray minimums
Compute over all subarrays of the minimum. There are subarrays, so enumerating is at best. Instead, flip the sum: for each index , count the subarrays in which is the minimum, and add times that count.
If is the minimum of , then ranges from just after the previous smaller element to , and ranges from to just before the next smaller element. With and choices respectively,
Duplicates. In [2, 2, 2] every subarray containing two 2s has two indices that equal its minimum. If both sides use "strictly smaller" as the boundary, each such subarray is counted twice; if both use "smaller or equal", it is counted zero times. The fix: make the boundary strict on one side and non-strict on the other. The convention used in this page: = previous index with (strictly smaller — so equal elements to the left are included in 's range), and = next index with (smaller or equal — equal elements to the right are excluded). Then each subarray is attributed to the leftmost occurrence of its minimum. Correctness proof below. Check: [3, 1, 2, 4] gives , matching brute force.
Sum of subarray ranges () is the same computation done twice, once with the comparisons flipped for maxima: .
Greedy with a budget: remove k digits
Remove exactly digits from a numeric string to make the result as small as possible. Greedy: scan left to right; while removals remain and the stack top is greater than the incoming digit, pop it (spending one removal); push the digit. If removals remain at the end, remove from the top (the stack is non-decreasing, so the largest digits are at the end). Strip leading zeros; return "0" if empty. For "1432219", : push 1; 4; 3 pops 4; 2 pops 3; 2; 1 pops 2 (third removal); 9 → "1219".
Why greedy is right (sketch). Compare two candidate results of the same length digit by digit: the first position where they differ decides. Suppose the stack holds and the next digit is with a removal available. Any solution that keeps here has in this position, while removing lets this position hold or something no larger (the suffix is unchanged); so removing is never worse — a standard exchange argument. Removing early digits beats removing later ones because earlier positions are more significant. Smallest subsequence of distinct characters (LeetCode 316/1081) is the same stack with the budget replaced by "only pop a character if it occurs again later" and a seen set preventing duplicates.
Other stack applications in brief
- Daily temperatures: NGE with distances:
ans[j] = i - jwhen pops . - Stock span (online): for each new price, span = distance to the previous strictly greater price. Pop while
price[top] <= price, span =i - top(ori + 1if empty). Each price is pushed once: amortized per day. - Next greater element II (circular): iterate from 0 to using
a[i % n], pushing only during the first pass. Elements still on the stack after the second pass are maxima with no greater element. - Trapping rain water with a stack: a decreasing stack of bar indices. When a taller bar arrives, pop the bottom of the "basin"
mid; if a left wall remains, water abovemidis(min(h[left], h[i]) - h[mid]) * (i - left - 1). This fills water in horizontal layers. The two-pointer method fills vertical columns and uses extra space; the stack method is space but generalises to streaming input from the left. - 132 pattern: scan from the right with a decreasing stack; when a larger value pops smaller ones, the largest popped value is the best candidate "2" (
third). If a later (further-left) value is smaller thanthird, a 132 exists. - Car fleet: sort cars by starting position descending, compute each car's arrival time; scanning from the front car backward, a car whose time is ≤ the fleet ahead's time merges into it. Keep a stack (really just the latest fleet time): a monotonic stack of strictly increasing times. The number of fleets is its size.
The monotonic deque: sliding window maximum
For each window , report its maximum. Keep a deque of indices such that (1) all indices are inside the current window and (2) their values are strictly decreasing from front to back. Then the front is the window maximum.
For each new index :
- Evict expired: pop the front while
front <= i - k. - Evict dominated: pop the back while
a[back] <= a[i]. - Push at the back.
- If , output
a[front].
flowchart LR
NEW["new index i"] --> EXP{"front <= i - k?"}
EXP -->|"yes"| PF["pop_front (left the window)"] --> EXP
EXP -->|"no"| DOM{"a[back] <= a[i]?"}
DOM -->|"yes"| PB["pop_back (can never be max again)"] --> DOM
DOM -->|"no"| PUSH["push_back i"]
PUSH --> OUT{"i >= k - 1?"}
OUT -->|"yes"| EMIT["output a[front]"]
Trace: sliding window maximum on [1, 3, -1, -3, 5, 3, 6, 7], (computed by script):
| i | a[i] | Expired from front | Dominated from back | Deque (indices) | Deque (values) | Output |
|---|---|---|---|---|---|---|
| 0 | 1 | – | – | [0] | [1] | – |
| 1 | 3 | – | 0 | [1] | [3] | – |
| 2 | −1 | – | – | [1, 2] | [3, −1] | 3 |
| 3 | −3 | – | – | [1, 2, 3] | [3, −1, −3] | 3 |
| 4 | 5 | 1 | 3, 2 | [4] | [5] | 5 |
| 5 | 3 | – | – | [4, 5] | [5, 3] | 5 |
| 6 | 6 | – | 5, 4 | [6] | [6] | 6 |
| 7 | 7 | – | 6 | [7] | [7] | 7 |
Output [3, 3, 5, 5, 6, 7]. At both kinds of eviction happen: index 1 (value 3) has left the window , and indices 3 and 2 are dominated by the new 5.
Shortest subarray with sum at least (negatives allowed). Let be prefix sums (, see Prefix Sums). We want the smallest with . Keep a deque of candidate left endpoints with increasing values. For each : while , record and pop the front (any later would give a longer subarray with this left end, so it is done); then while , pop the back ( is a later and no-larger left endpoint, so it dominates); push . Sliding window fails here because negatives break monotonicity of window sums; the deque restores it.
Constrained subsequence sum and Jump Game VI: dp[i] = nums[i] + max(dp[i-k..i-1]) (with a max(0, …) in the first). The inner max is a sliding window maximum over the dp array, maintained by a monotonic deque as dp values are produced, giving instead of . This is the simplest instance of the "monotonic queue optimisation" of dynamic programming, treated in depth in the later DP Optimizations lesson (Module 4, algorithms/dp/dp-optimizations).
Cartesian trees and ANSV
A Cartesian tree of an array (Vuillemin, 1980) is a binary tree that is a min-heap by value and whose inorder traversal is the array. Its root is the minimum; the left subtree is the Cartesian tree of the part to the left, the right subtree of the part to the right. The parent of is whichever of its previous-smaller and next-smaller elements is larger. So computing all nearest smaller values is building the Cartesian tree, and the stack algorithm does it in : the stack is always the right spine of the tree built so far. The Cartesian tree reduces range-minimum queries to lowest-common-ancestor queries, the route to preprocessing and RMQ described alongside the sparse table and segment tree in Advanced Data Structures.
The ladder: brute force → better → optimal
Ladder 1: next greater element
Rung 0: scan right from each index, . For each , walk until . On a strictly decreasing array every scan runs to the end: comparisons. On random input the expected scan is short, which is why brute force often passes small tests and then times out.
Rung 1 (detour): sorted structure, . Process indices from right to left, recording each index in a segment tree keyed by value that stores the smallest index seen per value; the NGE of is then the minimum index among values greater than , one range query. It works, but it is more complicated than the next rung and slower. It is worth knowing only because it generalises to queries the stack cannot answer (e.g. "next element greater than " for arbitrary ).
Rung 2: monotonic stack, . The waiting indices form a decreasing sequence; each arrival pops exactly those it answers. Each index pushed once, popped at most once.
| Rung | Idea | Time | Space |
|---|---|---|---|
| 0 | scan right from each index | worst | |
| 1 | balanced BST / segment tree over values | ||
| 2 | monotonic decreasing stack |
Ladder 2: sliding window maximum
Rung 0: recompute each window, . For , that is comparisons.
Rung 1: max-heap with lazy deletion, . Push (value, index) into a max-heap; before reading the top, pop it while its index is outside the window. Elements are removed lazily, so the heap can hold up to entries, giving total. (A balanced BST or multiset with true deletion gives .)
Rung 2: monotonic deque, . Observe that an element dominated by a newer, larger-or-equal element can never be a window maximum again — it will leave the window first and is never larger. Discarding dominated elements leaves a decreasing sequence; expired elements are always at the front. Each index enters and leaves the deque once.
| Rung | Idea | Time | Space |
|---|---|---|---|
| 0 | scan each window | ||
| 1 | max-heap with lazy deletion (or ordered multiset) | (multiset: ) | / |
| 2 | monotonic deque of indices |
The heap rung improves on rung 0 because it reuses work between windows; the deque improves on the heap because it uses the order of expiry (which the heap ignores) to discard candidates permanently.
Correctness
Next greater element
Invariant. After processing index : (a) the stack holds, in increasing index order, exactly those indices whose next greater element is not in ; (b) their values are non-increasing from bottom to top; (c) every index not on the stack has its correct answer recorded.
Maintenance. Let . Every stack index with : by (a) nothing in exceeds , and , so is 's NGE — recording it is correct and removing preserves (a). By (b) these indices form a contiguous run at the top, so the while loop finds exactly them. The remaining indices have , so is not their NGE and (a) holds for them; pushing (which has no answer yet) keeps (a), and since the new top's value , (b) holds. Termination: indices still on the stack have no greater element to their right; −1 is correct.
Largest rectangle
Claim. When index is popped by index with new top (or ), is the previous bar with , is the next bar with , and therefore every bar in has height : the computed rectangle is a real rectangle under the skyline.
Proof. Left side. When was pushed, it first popped every top bar with height ; this is the "previous smaller" row of the variants table with pop condition >=, so the bar left directly beneath was its previous strictly smaller bar. Nothing beneath changes while is on the stack, so that bar is still when is popped. Right side. Every bar pushed after and before found still on the stack, so it did not pop , meaning . And pops only because . So is the first bar after with height . Every bar strictly between and is by definition of previous-strictly-smaller, and every bar strictly between and is .
Every maximal rectangle is found. Take an optimal rectangle of height spanning the open interval , where and (or , ), and all bars inside have height , with at least one equal to . Let be the rightmost bar of height exactly inside it. By the claim, 's computed left boundary is its previous strictly smaller bar, which is (bars between and are ). Its computed right boundary is its next bar with height ; bars between and are because is the rightmost equal one, so that bar is (the sentinel at index plays this role at the end). The computed area is exactly the optimum. Non-rightmost equal bars compute a narrower width, but by the claim every computed area is a real rectangle, so no candidate ever overestimates.
This is why popping on equality (>=) is safe: some popped bars see a truncated right boundary, but the rightmost bar of each height always sees the true extent.
Sum of subarray minimums: no double counting
With = previous index with and = next index with :
Claim. Each subarray is counted by exactly one , namely the leftmost index in attaining the minimum .
Proof. Let be that leftmost index. All of are (strictly, since is leftmost), so ; all of are , so . Hence and : counts . Conversely, any other index in with lies to the right of , and means , so does not count . An index with cannot count it either, since its range stops before reaching the minimum.
The number of pairs counted by is , which gives the formula.
Sliding window maximum
Invariant. After processing , the deque holds exactly the indices such that no index has ; indices increase and values strictly decrease from front to back.
Evicted elements are never the answer. (1) An expired index is outside every future window, because windows only move right. (2) A dominated index (some with ) is in every future window only when also is ( expires later), and is at least as large — so is never needed as the reported maximum (ties report the same value). Hence the true maximum of the window is always in the deque, and since values decrease from the front, it is the front. Each index is pushed once and popped at most once, so .
Complexity
| Problem | Time | Extra space |
|---|---|---|
| Next greater / smaller, previous greater / smaller (all four) | stack (worst case: monotone input) | |
| Next greater element II (circular) | — iterations, pushes | |
| Largest rectangle in histogram | ||
| Maximal rectangle in matrix | ||
| Sum of subarray minimums / ranges | ||
| Remove digits / smallest subsequence | ||
| Trapping rain water (stack) | ||
| Sliding window maximum | ||
| Shortest subarray with sum ≥ K | ||
| DP with window max (constrained subsequence sum, jump game VI) |
All costs are worst-case except the per-step cost, which is amortized: one step can pop elements, but the total is linear. Constants are small — an array-backed stack of int indices sits in L1 cache for most of the scan, and the comparisons go through a[stack.top], an indirect but usually cached load. For the deque, use a ring buffer or a plain array with a head index (in JavaScript, never shift()); in C++ a std::deque<int> works but a std::vector<int> with a head index is often faster because MSVC's std::deque uses tiny 16-byte blocks.
Implementation
Four functions, the same test data in every language:
nextGreater(a)— next strictly greater value to the right, or −1.largestRectangle(h)— one-pass stack with a 0 sentinel.maxSlidingWindow(a, k)— monotonic deque of indices.sumSubarrayMins(a)— contribution technique mod , strict on the left, non-strict on the right, with 64-bit arithmetic. The large test (30,000 copies of 30,000) checks both the duplicate rule and overflow handling: the exact sum is , which overflows 32-bit integers.
from collections import deque
MOD = 1_000_000_007
def next_greater(a: list[int]) -> list[int]:
ans = [-1] * len(a)
stack: list[int] = [] # indices, values non-increasing
for i, v in enumerate(a):
while stack and a[stack[-1]] < v:
ans[stack.pop()] = v
stack.append(i)
return ans
def largest_rectangle(h: list[int]) -> int:
best = 0
stack: list[int] = [] # indices, heights increasing
for i in range(len(h) + 1):
cur = h[i] if i < len(h) else 0 # sentinel bar of height 0
while stack and h[stack[-1]] >= cur:
top = stack.pop()
left = stack[-1] if stack else -1
best = max(best, h[top] * (i - left - 1))
stack.append(i)
return best
def max_sliding_window(a: list[int], k: int) -> list[int]:
dq: deque[int] = deque() # indices, values strictly decreasing
out: list[int] = []
for i, v in enumerate(a):
while dq and dq[0] <= i - k: # expired
dq.popleft()
while dq and a[dq[-1]] <= v: # dominated
dq.pop()
dq.append(i)
if i >= k - 1:
out.append(a[dq[0]])
return out
def sum_subarray_mins(a: list[int]) -> int:
n = len(a)
left = [0] * n # i - previous strictly smaller
right = [0] * n # next smaller-or-equal - i
stack: list[int] = []
for i in range(n):
while stack and a[stack[-1]] > a[i]:
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack.clear()
for i in range(n - 1, -1, -1):
while stack and a[stack[-1]] >= a[i]:
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
total = 0
for i in range(n):
total = (total + a[i] * left[i] % MOD * right[i]) % MOD
return total
if __name__ == "__main__":
assert next_greater([2, 1, 2, 4, 3]) == [4, 2, 4, -1, -1]
assert next_greater([5, 4, 3]) == [-1, -1, -1]
assert next_greater([]) == []
assert largest_rectangle([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle([2, 4]) == 4
assert largest_rectangle([6, 2, 5, 4, 5, 1, 6]) == 12
assert largest_rectangle([1, 2, 3, 4, 5]) == 9
assert largest_rectangle([]) == 0
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9, 8, 7], 2) == [9, 8]
assert max_sliding_window([4, 4, 4], 2) == [4, 4]
assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([11, 81, 94, 43, 3]) == 444
assert sum_subarray_mins([2, 2, 2]) == 12
assert sum_subarray_mins([71, 55, 82, 55]) == 593
assert sum_subarray_mins([30000] * 30000) == 449905500
print("monotonic: all tests passed")
import java.util.ArrayDeque;
import java.util.Arrays;
public class MonotonicStackDeque {
static final long MOD = 1_000_000_007L;
static int[] nextGreater(int[] a) {
int n = a.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
int[] stack = new int[n]; // indices, values non-increasing
int top = 0;
for (int i = 0; i < n; i++) {
while (top > 0 && a[stack[top - 1]] < a[i]) ans[stack[--top]] = a[i];
stack[top++] = i;
}
return ans;
}
static long largestRectangle(int[] h) {
int n = h.length;
int[] stack = new int[n + 1]; // indices, heights increasing
int top = 0;
long best = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? h[i] : 0; // sentinel bar of height 0
while (top > 0 && h[stack[top - 1]] >= cur) {
int t = stack[--top];
int left = top > 0 ? stack[top - 1] : -1;
best = Math.max(best, (long) h[t] * (i - left - 1));
}
stack[top++] = i;
}
return best;
}
static int[] maxSlidingWindow(int[] a, int k) {
int n = a.length;
if (n == 0) return new int[0];
int[] out = new int[n - k + 1];
ArrayDeque<Integer> dq = new ArrayDeque<>(); // indices, values strictly decreasing
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // expired
while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast(); // dominated
dq.addLast(i);
if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
}
return out;
}
static long sumSubarrayMins(int[] a) {
int n = a.length;
long[] left = new long[n], right = new long[n];
int[] stack = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
while (top > 0 && a[stack[top - 1]] > a[i]) top--; // previous strictly smaller
left[i] = i - (top > 0 ? stack[top - 1] : -1);
stack[top++] = i;
}
top = 0;
for (int i = n - 1; i >= 0; i--) {
while (top > 0 && a[stack[top - 1]] >= a[i]) top--; // next smaller-or-equal
right[i] = (top > 0 ? stack[top - 1] : n) - i;
stack[top++] = i;
}
long total = 0;
for (int i = 0; i < n; i++) total = (total + a[i] * left[i] % MOD * right[i]) % MOD;
return total;
}
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
check(Arrays.equals(nextGreater(new int[]{2, 1, 2, 4, 3}), new int[]{4, 2, 4, -1, -1}), "nge");
check(Arrays.equals(nextGreater(new int[]{5, 4, 3}), new int[]{-1, -1, -1}), "nge decreasing");
check(nextGreater(new int[0]).length == 0, "nge empty");
check(largestRectangle(new int[]{2, 1, 5, 6, 2, 3}) == 10, "lr 10");
check(largestRectangle(new int[]{2, 4}) == 4, "lr 4");
check(largestRectangle(new int[]{6, 2, 5, 4, 5, 1, 6}) == 12, "lr 12");
check(largestRectangle(new int[]{1, 2, 3, 4, 5}) == 9, "lr 9");
check(largestRectangle(new int[0]) == 0, "lr empty");
check(Arrays.equals(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3), new int[]{3, 3, 5, 5, 6, 7}), "swm");
check(Arrays.equals(maxSlidingWindow(new int[]{1}, 1), new int[]{1}), "swm single");
check(Arrays.equals(maxSlidingWindow(new int[]{9, 8, 7}, 2), new int[]{9, 8}), "swm decreasing");
check(Arrays.equals(maxSlidingWindow(new int[]{4, 4, 4}, 2), new int[]{4, 4}), "swm equal");
check(sumSubarrayMins(new int[]{3, 1, 2, 4}) == 17, "ssm 17");
check(sumSubarrayMins(new int[]{11, 81, 94, 43, 3}) == 444, "ssm 444");
check(sumSubarrayMins(new int[]{2, 2, 2}) == 12, "ssm dup");
check(sumSubarrayMins(new int[]{71, 55, 82, 55}) == 593, "ssm 593");
int[] big = new int[30000];
Arrays.fill(big, 30000);
check(sumSubarrayMins(big) == 449905500L, "ssm big");
System.out.println("monotonic: all tests passed");
}
}
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <string>
#include <vector>
static void check(bool cond, const std::string& msg) {
if (!cond) { std::cerr << "FAIL: " << msg << "\n"; std::exit(1); }
}
constexpr std::int64_t MOD = 1'000'000'007;
std::vector<int> nextGreater(const std::vector<int>& a) {
std::vector<int> ans(a.size(), -1);
std::vector<int> st; // indices, values non-increasing
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
while (!st.empty() && a[st.back()] < a[i]) { ans[st.back()] = a[i]; st.pop_back(); }
st.push_back(i);
}
return ans;
}
std::int64_t largestRectangle(const std::vector<int>& h) {
const int n = static_cast<int>(h.size());
std::vector<int> st; // indices, heights increasing
std::int64_t best = 0;
for (int i = 0; i <= n; ++i) {
int cur = i < n ? h[i] : 0; // sentinel bar of height 0
while (!st.empty() && h[st.back()] >= cur) {
int t = st.back(); st.pop_back();
int left = st.empty() ? -1 : st.back();
best = std::max(best, static_cast<std::int64_t>(h[t]) * (i - left - 1));
}
st.push_back(i);
}
return best;
}
std::vector<int> maxSlidingWindow(const std::vector<int>& a, int k) {
std::vector<int> out;
std::deque<int> dq; // indices, values strictly decreasing
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // expired
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // dominated
dq.push_back(i);
if (i >= k - 1) out.push_back(a[dq.front()]);
}
return out;
}
std::int64_t sumSubarrayMins(const std::vector<int>& a) {
const int n = static_cast<int>(a.size());
std::vector<std::int64_t> left(n), right(n);
std::vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.back()] > a[i]) st.pop_back(); // previous strictly smaller
left[i] = i - (st.empty() ? -1 : st.back());
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back(); // next smaller-or-equal
right[i] = (st.empty() ? n : st.back()) - i;
st.push_back(i);
}
std::int64_t total = 0;
for (int i = 0; i < n; ++i) total = (total + a[i] * left[i] % MOD * right[i]) % MOD;
return total;
}
int main() {
check(nextGreater({2, 1, 2, 4, 3}) == std::vector<int>{4, 2, 4, -1, -1}, "nge");
check(nextGreater({5, 4, 3}) == std::vector<int>{-1, -1, -1}, "nge decreasing");
check(nextGreater({}).empty(), "nge empty");
check(largestRectangle({2, 1, 5, 6, 2, 3}) == 10, "lr 10");
check(largestRectangle({2, 4}) == 4, "lr 4");
check(largestRectangle({6, 2, 5, 4, 5, 1, 6}) == 12, "lr 12");
check(largestRectangle({1, 2, 3, 4, 5}) == 9, "lr 9");
check(largestRectangle({}) == 0, "lr empty");
check(maxSlidingWindow({1, 3, -1, -3, 5, 3, 6, 7}, 3) == std::vector<int>{3, 3, 5, 5, 6, 7}, "swm");
check(maxSlidingWindow({1}, 1) == std::vector<int>{1}, "swm single");
check(maxSlidingWindow({9, 8, 7}, 2) == std::vector<int>{9, 8}, "swm decreasing");
check(maxSlidingWindow({4, 4, 4}, 2) == std::vector<int>{4, 4}, "swm equal");
check(sumSubarrayMins({3, 1, 2, 4}) == 17, "ssm 17");
check(sumSubarrayMins({11, 81, 94, 43, 3}) == 444, "ssm 444");
check(sumSubarrayMins({2, 2, 2}) == 12, "ssm dup");
check(sumSubarrayMins({71, 55, 82, 55}) == 593, "ssm 593");
check(sumSubarrayMins(std::vector<int>(30000, 30000)) == 449905500, "ssm big");
std::cout << "monotonic: all tests passed\n";
return 0;
}
const MOD = 1_000_000_007n;
function nextGreater(a: number[]): number[] {
const ans = new Array<number>(a.length).fill(-1);
const stack: number[] = []; // indices, values non-increasing
for (let i = 0; i < a.length; i++) {
while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) ans[stack.pop()!] = a[i];
stack.push(i);
}
return ans;
}
function largestRectangle(h: number[]): number {
const stack: number[] = []; // indices, heights increasing
let best = 0;
for (let i = 0; i <= h.length; i++) {
const cur = i < h.length ? h[i] : 0; // sentinel bar of height 0
while (stack.length > 0 && h[stack[stack.length - 1]] >= cur) {
const t = stack.pop()!;
const left = stack.length > 0 ? stack[stack.length - 1] : -1;
best = Math.max(best, h[t] * (i - left - 1));
}
stack.push(i);
}
return best;
}
function maxSlidingWindow(a: number[], k: number): number[] {
// deque as an array plus a head index: never use shift() here
const dq: number[] = [];
let head = 0;
const out: number[] = [];
for (let i = 0; i < a.length; i++) {
while (head < dq.length && dq[head] <= i - k) head++; // expired
while (head < dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop(); // dominated
dq.push(i);
if (i >= k - 1) out.push(a[dq[head]]);
}
return out;
}
function sumSubarrayMins(a: number[]): number {
const n = a.length;
const left = new Array<number>(n);
const right = new Array<number>(n);
let stack: number[] = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && a[stack[stack.length - 1]] > a[i]) stack.pop(); // previous strictly smaller
left[i] = i - (stack.length > 0 ? stack[stack.length - 1] : -1);
stack.push(i);
}
stack = [];
for (let i = n - 1; i >= 0; i--) {
while (stack.length > 0 && a[stack[stack.length - 1]] >= a[i]) stack.pop(); // next smaller-or-equal
right[i] = (stack.length > 0 ? stack[stack.length - 1] : n) - i;
stack.push(i);
}
// BigInt: a[i] * left * right can exceed 2^53 for large inputs
let total = 0n;
for (let i = 0; i < n; i++) total = (total + BigInt(a[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;
return Number(total);
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAIL: " + msg);
}
const eq = (x: number[], y: number[]): boolean => JSON.stringify(x) === JSON.stringify(y);
check(eq(nextGreater([2, 1, 2, 4, 3]), [4, 2, 4, -1, -1]), "nge");
check(eq(nextGreater([5, 4, 3]), [-1, -1, -1]), "nge decreasing");
check(eq(nextGreater([]), []), "nge empty");
check(largestRectangle([2, 1, 5, 6, 2, 3]) === 10, "lr 10");
check(largestRectangle([2, 4]) === 4, "lr 4");
check(largestRectangle([6, 2, 5, 4, 5, 1, 6]) === 12, "lr 12");
check(largestRectangle([1, 2, 3, 4, 5]) === 9, "lr 9");
check(largestRectangle([]) === 0, "lr empty");
check(eq(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]), "swm");
check(eq(maxSlidingWindow([1], 1), [1]), "swm single");
check(eq(maxSlidingWindow([9, 8, 7], 2), [9, 8]), "swm decreasing");
check(eq(maxSlidingWindow([4, 4, 4], 2), [4, 4]), "swm equal");
check(sumSubarrayMins([3, 1, 2, 4]) === 17, "ssm 17");
check(sumSubarrayMins([11, 81, 94, 43, 3]) === 444, "ssm 444");
check(sumSubarrayMins([2, 2, 2]) === 12, "ssm dup");
check(sumSubarrayMins([71, 55, 82, 55]) === 593, "ssm 593");
check(sumSubarrayMins(new Array<number>(30000).fill(30000)) === 449905500, "ssm big");
console.log("monotonic: all tests passed");
Implementation notes:
- Store indices, not values. Every function above pushes indices. Distances (daily temperatures, span), widths (rectangles), and window expiry all need positions; values are always recoverable as
a[idx]. - In Java and C++ the stack is a pre-sized
int[]/std::vector<int>with a manual top pointer, which avoids boxing (ArrayDeque<Integer>boxes every index). The deque in Java is kept asArrayDeque<Integer>for readability; for hot paths use anint[]with head and tail indices. - The modular product is computed as
a * left % MOD * right % MODin 64-bit:a * leftis at most , reduced below , then timesrightstays below . With larger constraints reduce each factor first. TypeScript usesBigIntbecausenumberloses exactness above .
Variant: both neighbours in one pass
def prev_next_smaller(a: list[int]) -> tuple[list[int], list[int]]:
"""prev[i]: index of previous element <= a[i] (or -1), from the post-pop top.
nxt[i]: index of next element < a[i] (or n), from the pop event."""
n = len(a)
prev, nxt = [-1] * n, [n] * n
stack: list[int] = []
for i, v in enumerate(a):
while stack and a[stack[-1]] > v:
nxt[stack.pop()] = i
prev[i] = stack[-1] if stack else -1
stack.append(i)
return prev, nxt
p, q = prev_next_smaller([3, 1, 2, 1, 4])
assert p == [-1, -1, 1, 1, 3]
assert q == [1, 5, 3, 5, 5]
Note the asymmetry the strictness rule predicts: popping on strict > gives a strict "next smaller" (index 1's value 1 is not ended by the later 1 at index 3) and a non-strict "previous smaller-or-equal" (index 3's previous is index 1, an equal value).
Real-world uses
Stock span and technical analysis. The stock span — how many consecutive prior days had a price ≤ today's — is the textbook monotonic-stack problem and a real indicator family: "N-day high" breakout signals, drawdown duration, and "days since a higher close" are all previous-greater-element queries computed online in amortized per tick.
Rate-of-change alerts and range-max over time windows. Monitoring systems evaluate rules like "the maximum CPU over the last 5 minutes exceeds 90%" or "the minimum free memory over the last hour dropped below X" continuously. Over a stream of samples with fixed-size or time-based windows, a monotonic deque gives each window's extreme in amortized per sample and memory, versus re-scanning the window. Systems that need many window sizes at once typically precompute downsampled rollups instead; the deque is the per-series inner loop. The same structure underlies the sliding-window rate limiters' max/min variants discussed in Rate Limiting.
Histogram-based layout. Finding the largest empty rectangle in an occupancy grid (placing a window or a widget in free screen space, packing in 2-D bin layouts, finding free regions in a floor plan or a VLSI layout) is maximal-rectangle-in-a-binary-matrix: one histogram per row, one stack pass each.
Parallel algorithms: ANSV. Berkman, Schieber and Vishkin (1993) showed that all nearest smaller values can be computed in time with processors on a CRCW PRAM and used it as a primitive for parallel merging, monotone polygon triangulation, Cartesian-tree construction and parenthesis matching. Modern GPU and multicore libraries implement ANSV-style primitives for the same reasons.
Cartesian trees and RMQ. The linear-time Cartesian tree construction (the stack is the right spine) is the first step of the classic range-minimum-query structure: build the Cartesian tree, then answer RMQ as LCA. It also builds treaps from sorted input in and underlies suffix-array LCP-interval algorithms in string processing. See Advanced Data Structures for segment trees and sparse tables, the more common RMQ tools.
Compilers and editors. "Find the matching / enclosing bracket" and "nearest enclosing scope" are nearest-smaller-value queries on the nesting-depth array; editors that colour matching brackets in large files compute them with a stack in one pass.
Pitfalls & edge cases
- Strict versus non-strict with duplicates. Using "strictly smaller" on both sides in sum-of-subarray-minimums double counts every subarray with a repeated minimum (
[2, 2, 2]gives 20 instead of 12); using non-strict on both sides under-counts. Make one side strict and the other non-strict, and test[2, 2, 2]. - Circular arrays. Next greater element II needs two passes (
i % nover indices). Push only in the first pass, or you double the stack and may record an index's own value as its answer. - Forgetting the sentinel / final flush. In largest rectangle, elements still on the stack at the end have right boundary . Either append a 0 bar or run a cleanup loop.
[1, 2, 3, 4, 5]returns 0 without it. - Storing values instead of indices. You lose widths, distances and expiry. Store indices; read values through them.
- Window eviction by value. Some deque solutions store values and evict "if
dq[0] == a[i-k]". This breaks with duplicates unless the dominance pop is strict. Evict by index:dq[0] <= i - k. - Off-by-one in the window test. The window ending at is , so the front is expired when
front <= i - k(equivalentlyfront < i - k + 1). Output starts at . - Overflow in contribution sums.
a[i] * left[i] * right[i]can reach for and values , and more for larger constraints. Use 64-bit (long,int64_t,BigInt) and reduce mod after each multiplication. JavaScriptnumbersilently loses precision above . - Remove k digits leftovers. If removals remain after the scan (input already non-decreasing, e.g.
"12345"), remove from the end. Then strip leading zeros, and return"0"for an empty result. - Using the wrong monotonic direction. Next greater needs a decreasing stack (larger elements stay at the bottom); next smaller needs an increasing stack. If your answers are all −1 on an obviously non-trivial input, the direction is flipped.
shift()as deque pop in JavaScript. Turns the algorithm into or worse; use a head index.- Empty input and . Guard: return an empty result, and decide (and document) what the window problem returns for .
- Popping the stack top before reading the left boundary. In largest rectangle the left boundary is the top after popping
t; read it after the pop, not before.
Variations
- Monotonic queue in DP optimisation. Whenever a DP transition is
dp[i] = f(i) + max_{j ∈ [i-k, i-1]} g(j)with a sliding range of , a monotonic deque over makes it . Bounded knapsack with the "residue class" trick and many "jump with reach " problems use it. This generalises in the Module 4 DP Optimizations lesson. - Two monotonic deques for min and max in the same window. "Longest subarray where max − min ≤ limit" (LeetCode 1438): grow the right end, maintain a max-deque and a min-deque; while
max − min > limit, advance the left end and expire deque fronts. with the sliding window template. - Monotonic stack on trees. During a DFS, the root-to-node path is a stack; keeping it monotonic (with rollback on return) answers "nearest ancestor with a greater value" for every node in total if you binary-search the path or keep a monotone path with undo records.
- Offline queries. "For each query , the first index ≥ with value > " cannot be answered by a single stack pass, but sorting queries by descending and maintaining the monotonic stack as decreases lets you binary-search the stack (which is sorted) for each query: .
- Min-stack / min-queue. The min-stack from Stacks stores running minimums; a min-queue is either two min-stacks or a monotonic increasing deque.
- Cartesian tree construction. Same loop; the popped run becomes the left child of the new node, and the new node becomes the right child of the top.
- Monotonic stack with counts. For "sum of subarray minimums" in a single pass, push (value, count) pairs and maintain the running sum of minimums of subarrays ending at : with one pass instead of two.
Practice ladder
Each problem is described in my own words. Solutions are Python and are run as part of this page's checks.
1. Next Greater Element II (LeetCode 503) — Medium. The array is circular. Teaches index doubling.
Hint
Iterate over with a[i % n]; push only when .
Solution
def next_greater_circular(a: list[int]) -> list[int]:
n = len(a)
ans = [-1] * n
stack: list[int] = []
for i in range(2 * n):
v = a[i % n]
while stack and a[stack[-1]] < v:
ans[stack.pop()] = v
if i < n:
stack.append(i)
return ans
assert next_greater_circular([1, 2, 1]) == [2, -1, 2]
assert next_greater_circular([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]
assert next_greater_circular([5, 5]) == [-1, -1]
Time — iterations, pushes, at most pops. Space .
2. Online Stock Span (LeetCode 901) — Medium. Streaming previous-greater with span lengths. Teaches the online form and (value, span) pairs.
Hint
Stack of (price, span). On a new price, pop while top.price <= price, adding their spans to the current span (starting from 1).
3. Largest Rectangle in Histogram (LeetCode 84) — Hard. The canonical implementation above. Teaches boundaries from nearest smaller bars and the sentinel.
Hint
Increasing stack; on pop, width = i − newTop − 1. Append a 0.
4. Maximal Rectangle (LeetCode 85) — Hard. Largest all-1 rectangle in a binary matrix. Teaches reduction to a histogram per row.
Hint
heights[c] = heights[c] + 1 if the cell is 1 else 0; run problem 5 on each row.
Solution
def maximal_rectangle(matrix: list[list[str]]) -> int:
if not matrix:
return 0
cols = len(matrix[0])
heights = [0] * cols
best = 0
for row in matrix:
for c in range(cols):
heights[c] = heights[c] + 1 if row[c] == "1" else 0
stack: list[int] = []
for i in range(cols + 1):
cur = heights[i] if i < cols else 0
while stack and heights[stack[-1]] >= cur:
top = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[top] * (i - left - 1))
stack.append(i)
return best
grid = [list("10100"), list("10111"), list("11111"), list("10010")]
assert maximal_rectangle(grid) == 6
assert maximal_rectangle([["0"]]) == 0
assert maximal_rectangle([["1", "1"], ["1", "1"]]) == 4
Time , space .
5. Sum of Subarray Minimums (LeetCode 907) — Medium. The contribution technique with duplicates and a modulus. Solved by the canonical implementation.
Hint
Previous strictly smaller on the left, next smaller-or-equal on the right; add a[i] * left * right.
6. Sum of Subarray Ranges (LeetCode 2104) — Medium. Sum of max − min over all subarrays. Teaches running the contribution technique for both extremes.
Hint
Compute the sum of subarray maxima (flip both comparisons) minus the sum of subarray minima. No modulus needed but values can be negative.
Solution
def sum_extremes(a: list[int], sign: int) -> int:
"""sign = 1: sum of subarray minima; sign = -1: sum of subarray maxima."""
b = [sign * x for x in a]
n = len(b)
left, right, st = [0] * n, [0] * n, []
for i in range(n):
while st and b[st[-1]] > b[i]:
st.pop()
left[i] = i - (st[-1] if st else -1)
st.append(i)
st = []
for i in range(n - 1, -1, -1):
while st and b[st[-1]] >= b[i]:
st.pop()
right[i] = (st[-1] if st else n) - i
st.append(i)
return sign * sum(b[i] * left[i] * right[i] for i in range(n))
def sub_array_ranges(a: list[int]) -> int:
return sum_extremes(a, -1) - sum_extremes(a, 1)
assert sub_array_ranges([1, 2, 3]) == 4
assert sub_array_ranges([1, 3, 3]) == 4
assert sub_array_ranges([4, -2, -3, 4, 1]) == 59
Time , space . Negating the array turns "maximum" into "minimum", so one function serves both.
7. Remove K Digits (LeetCode 402) — Medium. Teaches greedy popping with a budget and the leftover/leading-zero cleanup.
Hint
Pop while budget remains and top > digit. Afterwards trim the remaining budget from the end, strip leading zeros, default to "0".
Solution
def remove_k_digits(num: str, k: int) -> str:
stack: list[str] = []
for d in num:
while k and stack and stack[-1] > d:
stack.pop()
k -= 1
stack.append(d)
if k:
stack = stack[:-k]
return "".join(stack).lstrip("0") or "0"
assert remove_k_digits("1432219", 3) == "1219"
assert remove_k_digits("10200", 1) == "200"
assert remove_k_digits("10", 2) == "0"
assert remove_k_digits("12345", 2) == "123"
Time , space .
8. Remove Duplicate Letters (LeetCode 316) — Medium. Lexicographically smallest subsequence with each distinct letter exactly once. Teaches "pop only if it reappears later".
Hint
Precompute each letter's last index. Skip letters already in the stack; pop while top > c and top occurs again after the current position.
9. Trapping Rain Water (LeetCode 42) — Hard. Teaches the layered stack method; compare with the two-pointer solution.
Hint
Decreasing stack. When a taller bar arrives, pop the basin floor; if a left wall remains, add (min(left, right) − floor) × width.
Solution
def trap(h: list[int]) -> int:
water = 0
stack: list[int] = []
for i, cur in enumerate(h):
while stack and h[stack[-1]] < cur:
floor = h[stack.pop()]
if not stack:
break
left = stack[-1]
water += (min(h[left], cur) - floor) * (i - left - 1)
stack.append(i)
return water
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([]) == 0
assert trap([3, 3, 3]) == 0
Time , space (two pointers achieves space).
10. 132 Pattern (LeetCode 456) — Medium. Teaches scanning right-to-left with a decreasing stack and a "best middle" variable.
Hint
From the right, maintain third = the largest value popped so far. If the current value is less than third, return true; else pop everything smaller than it into third, then push.
Solution
def find132pattern(a: list[int]) -> bool:
third = float("-inf")
stack: list[int] = []
for v in reversed(a):
if v < third:
return True
while stack and stack[-1] < v:
third = stack.pop()
stack.append(v)
return False
assert not find132pattern([1, 2, 3, 4])
assert find132pattern([3, 1, 4, 2])
assert find132pattern([-1, 3, 2, 0])
assert not find132pattern([1, 0, 1, -4, -3])
Time . third was popped by a larger value lying to its left in the array, so a still-further-left v < third completes a 1-3-2.
11. Car Fleet (LeetCode 853) — Medium. Teaches sorting then a monotonic stack of arrival times.
Hint
Sort by position descending; a car whose arrival time is ≤ the current fleet's time joins it; otherwise it starts a new fleet.
12. Sliding Window Maximum (LeetCode 239) — Hard. The canonical deque implementation.
Hint
Evict expired from the front, dominated from the back, push, read the front.
13. Shortest Subarray with Sum at Least K (LeetCode 862) — Hard. Prefix sums with an increasing deque. Teaches why sliding window fails with negatives.
Hint
For each prefix index : pop front while P[j] − P[front] ≥ K (record), pop back while P[back] ≥ P[j], push .
Solution
from collections import deque
def shortest_subarray(nums: list[int], k: int) -> int:
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
best = len(nums) + 1
dq: deque[int] = deque()
for j, pj in enumerate(prefix):
while dq and pj - prefix[dq[0]] >= k:
best = min(best, j - dq.popleft())
while dq and prefix[dq[-1]] >= pj:
dq.pop()
dq.append(j)
return best if best <= len(nums) else -1
assert shortest_subarray([1], 1) == 1
assert shortest_subarray([1, 2], 4) == -1
assert shortest_subarray([2, -1, 2], 3) == 3
assert shortest_subarray([84, -37, 32, 40, 95], 167) == 3
Time , space .
14. Longest Continuous Subarray With Absolute Diff ≤ Limit (LeetCode 1438) — Medium. Two deques (max and min) with a variable window.
Hint
Max-deque decreasing, min-deque increasing; while max − min > limit advance the left end and expire fronts equal to it by index.
Solution
from collections import deque
def longest_subarray(nums: list[int], limit: int) -> int:
mx: deque[int] = deque()
mn: deque[int] = deque()
left = best = 0
for right, v in enumerate(nums):
while mx and nums[mx[-1]] <= v:
mx.pop()
while mn and nums[mn[-1]] >= v:
mn.pop()
mx.append(right)
mn.append(right)
while nums[mx[0]] - nums[mn[0]] > limit:
left += 1
if mx[0] < left:
mx.popleft()
if mn[0] < left:
mn.popleft()
best = max(best, right - left + 1)
return best
assert longest_subarray([8, 2, 4, 7], 4) == 2
assert longest_subarray([10, 1, 2, 4, 7, 2], 5) == 4
assert longest_subarray([4, 2, 2, 2, 4, 4, 2, 2], 0) == 3
Time , space .
15. Jump Game VI (LeetCode 1696) — Medium. DP with a window maximum over the last dp values. Teaches the monotonic deque as a DP accelerator.
Hint
dp[i] = nums[i] + max(dp[i−k..i−1]); keep a decreasing deque of dp indices.
Solution
from collections import deque
def max_result(nums: list[int], k: int) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
dq: deque[int] = deque([0])
for i in range(1, len(nums)):
while dq[0] < i - k:
dq.popleft()
dp[i] = nums[i] + dp[dq[0]]
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[-1]
assert max_result([1, -1, -2, 4, -7, 3], 2) == 7
assert max_result([10, -5, -2, 4, 0, 3], 3) == 17
assert max_result([1, -5, -20, 4, -1, 3, -6, -3], 2) == 0
Time , space . Constrained Subsequence Sum (LeetCode 1425) is the same with max(0, …).
Going further: Next Greater Element I (LeetCode 496) is the easy warm-up (NGE plus a value-to-answer map), Daily Temperatures (LeetCode 739) is NGE with distances (record i - j when pops ), and Maximum Subarray Min-Product (LeetCode 1856) combines each element's nearest-smaller boundaries with prefix sums.
Common mistakes & interview follow-ups
"What if the input is a stream?" Next-greater answers for an element arrive later in the stream, so emit them when the element is popped; elements still on the stack are "pending". Previous-greater (stock span) is naturally online with amortized per element. Sliding window max is online with memory.
"What if memory is limited to ?" Trapping rain water has an -space two-pointer solution. Next greater element does not in general: the stack can legitimately hold pending elements (decreasing input), and any one-pass algorithm must remember them.
"Can you do sliding window max without a deque?" Yes: block decomposition. Split the array into blocks of size ; precompute prefix maxima within each block from the left and suffix maxima from the right; any window spans at most two blocks, so its max is max(suffix[i], prefix[i + k − 1]). time, space, no data structure, and trivially parallel.
"How do you handle duplicates in sum of subarray minimums?" Strict on one side, non-strict on the other, so each subarray is attributed to exactly one occurrence of its minimum (leftmost or rightmost, depending on which side is strict). Show [2, 2, 2] → 12.
"Generalise largest rectangle to 2-D." Maximal rectangle: histogram per row, . For the largest square, a DP is simpler: dp[r][c] = 1 + min(up, left, diag).
"Range maximum queries on arbitrary ranges, not sliding windows?" The deque requires both window ends to move monotonically. For arbitrary ranges use a sparse table ( query, static) or a segment tree (, supports updates) — see Advanced Data Structures.
"Why is this when there is a nested loop?" Each index is pushed once and popped at most once; total pops ≤ total pushes = . Be ready to state it in potential-function form.
"Return the subarray / rectangle, not just its size." Record the indices alongside best when you update it: (left + 1, i − 1, h[top]) for the rectangle.
Common mistakes seen in interviews: monotonic direction flipped; comparing values when the stack holds indices (stack[-1] < v instead of a[stack[-1]] < v); forgetting the sentinel; strict/non-strict mismatch; evicting by value from the deque; and int overflow in contribution sums.
Quick quiz
- For next greater element, is the stack increasing or decreasing from bottom to top, and why is it forced?
Answer
Non-increasing. If a smaller element sat below a larger one, the larger one arrived later and is its next greater element, so it would have popped the smaller one on arrival. Hence the elements still waiting form a non-increasing sequence.
- In the histogram
[2, 1, 5, 6, 2, 3], which bar computes the winning area 10, and at which index is it popped?
Answer
Bar 2 (height 5) is popped at (height 2). The new top is bar 1, so width and area .
- Sum of subarray minimums on
[2, 2, 2]with "strictly smaller" boundaries on both sides — what do you get and why is it wrong?
Answer
With strict boundaries on both sides each index extends over all its equal neighbours: left counts are 1, 2, 3 and right counts 3, 2, 1, giving . The correct answer is 12: each subarray containing several 2s is counted once per 2 it contains. One side must be non-strict.
- In sliding window max, why can an element popped from the back never be a future answer?
Answer
It was popped by a newer element with a value at least as large. The newer one stays in every window the older one is in (it expires later), so the older one can never be strictly the maximum.
- Why does sliding window fail for "shortest subarray with sum ≥ K" when negatives are allowed, and what does the deque fix?
Answer
With negatives, extending a window can decrease its sum and shrinking it can increase it, so the two-pointer monotonicity breaks. The deque of prefix indices with increasing prefix values keeps only left endpoints that could still be optimal: a later, smaller prefix dominates an earlier larger one, and a left endpoint that has already produced a valid subarray can be retired.
Further reading / sources
- O. Berkman, B. Schieber & U. Vishkin, "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms 14(3):344–370, 1993. DOI 10.1006/jagm.1993.1018.
- H. N. Gabow, J. L. Bentley & R. E. Tarjan, "Scaling and related techniques for geometry problems", STOC 1984 — Cartesian trees for RMQ.
- J. Vuillemin, "A unifying look at data structures", Communications of the ACM 23(4), 1980 — Cartesian trees.
- cp-algorithms: Minimum stack / Minimum queue and Finding the largest zero submatrix.
- Wikipedia: All nearest smaller values and Cartesian tree.
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., Chapter 16 (amortized analysis — the aggregate and potential methods used in the key lemma).
- Sedgewick & Wayne, Algorithms, 4th ed., §1.3 (stacks and deques) and §1.4 (amortized analysis).
Prev: Queues, Deques & Circular Buffers · Next: Intervals
Related: Module 1 — Linear Data Structures · Stacks · Sliding Window · Two Pointers · Prefix Sums & Difference Arrays · Matrices & 2D Grids · Advanced Data Structures · Heaps & Priority Queues · Arrays & Strings · DSA: Zero to Mastery