-
Notifications
You must be signed in to change notification settings - Fork 0
022 — Monotonic Stack
This is the last chapter in this batch, and it closes on a pattern that looks like a small tweak to a plain stack (Stacks) but unlocks a genuinely different class of problem: finding, for every element, the nearest element to its left or right that's bigger or smaller than it — in a single pass, without ever comparing every pair.
Picture a stack of pancakes being built one at a time, fresh off the griddle, and you have a rule: no pancake is allowed to sit directly on top of a smaller one — it looks silly and the stack gets wobbly. So every time a new pancake arrives, before placing it, you lift off (and set aside) every pancake on top that's smaller than the new one, and only then place the new pancake down. The pancakes you just lifted off aren't gone — the moment you removed each one, you learned something valuable: "the pancake that finally knocked you off the stack was the first thing bigger than you, coming from your right." That fact — the first bigger (or smaller) element to one side — is exactly what a monotonic stack computes, for every element, in one single pass through the data.
Monotonic Stack is a strong reach when you see:
- "Next greater element" / "next smaller element" (or "previous greater/smaller") — almost a literal keyword match. Any phrasing asking, for every element, what's the nearest element to one side that's bigger or smaller.
- "Daily temperatures" / "how many days until a warmer day" style problems — asking for the distance to the next greater element, not just its value, is the same pattern with the stack holding indices instead of values.
- "Largest rectangle in histogram" / "trapping rain water" — anywhere you need, for each bar, the nearest shorter bar on both sides (to know how far a rectangle can extend, or how much water a "wall" configuration can trap) — a classic sign the stack should hold indices of a currently-increasing (or decreasing) run of bar heights.
- "Remove k digits to make the smallest number", or any "maintain a strictly increasing/decreasing subsequence by discarding elements greedily as you scan" framing — the stack literally is the answer being built, with earlier entries popped off the instant a new element proves them suboptimal.
The unifying tell: you need, for every element, information about the nearest element to one side satisfying a comparison (bigger, smaller) — and a plain nested loop checking every pair would be O(n²), when a single pass with a stack that only ever grows monotonically gets it down to O(n).
Finding the next greater element for each value in [2, 1, 5, 3, 4], using a stack that holds indices, kept monotonically decreasing (bottom-to-top) in value:
array: [2, 1, 5, 3, 4]
index: 0 1 2 3 4
i=0: stack empty → push 0. stack (indices): [0] values: [2]
i=1: arr[1]=1 < arr[stack.top]=2 → doesn't beat top → push 1.
stack: [0,1] values: [2,1]
i=2: arr[2]=5 > arr[1]=1 → POP 1, result[1] = 5 (next greater for index 1)
arr[2]=5 > arr[0]=2 → POP 0, result[0] = 5 (next greater for index 0)
stack empty → push 2. stack: [2] values: [5]
i=3: arr[3]=3 < arr[2]=5 → doesn't beat top → push 3.
stack: [2,3] values: [5,3]
i=4: arr[4]=4 > arr[3]=3 → POP 3, result[3] = 4 (next greater for index 3)
arr[4]=4 < arr[2]=5 → doesn't beat top → push 4.
stack: [2,4] values: [5,4]
Leftover stack [2,4] → no next-greater element exists for indices 2, 4 → -1
result: [5, 5, -1, 4, -1]
Every index is pushed once and popped at most once — that's the O(n) guarantee.
func monotonicStackTemplate(_ array: [Int]) -> [Int] {
var result = Array(repeating: -1, count: array.count) // 🔧 Fill in: default when no answer exists.
var stack: [Int] = [] // holds INDICES, kept monotonic by array[index]
for i in 0..<array.count {
// 🔧 Fill in: the comparison that decides when to pop. This example finds
// the NEXT GREATER element, so pop while the new value beats the stack's top.
while let top = stack.last, array[i] > array[top] {
stack.removeLast()
result[top] = array[i] // 🔧 array[i] is the answer for whatever got popped.
}
stack.append(i)
}
return result // 🔧 Anything left on the stack at the end never found an answer.
}The skeleton never changes: a stack of indices, one forward pass, and a while loop that pops (and resolves) every stack entry the current element beats, before pushing the current index. Flip the comparison (< instead of >) to find the next smaller element instead; iterate right-to-left instead of left-to-right to find the previous greater/smaller element instead of the next one.
Daily Temperatures — given an array temperatures, return an array answer where answer[i] is the number of days you'd have to wait after day i for a warmer temperature. If there's no future day like that, answer[i] == 0.
func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
var answer = Array(repeating: 0, count: temperatures.count)
var stack: [Int] = [] // indices of days still waiting for a warmer day
for i in 0..<temperatures.count {
while let top = stack.last, temperatures[i] > temperatures[top] {
stack.removeLast()
answer[top] = i - top // distance in days, not the temperature itself
}
stack.append(i)
}
return answer
}
// smoke test
print(dailyTemperatures([73,74,75,71,69,72,76,73])) // [1,1,4,2,1,1,0,0]
print(dailyTemperatures([30,40,50,60])) // [1,1,1,0]
print(dailyTemperatures([30,60,90])) // [1,1,0]Mapped onto the template: identical skeleton — a stack of indices, a while loop popping every day beaten by the current (warmer) day. The one change is what gets stored on resolution: the generic template stores array[i] (the value that won), but this problem asks for the wait time, so answer[top] = i - top stores the distance between the popped index and the current index instead. answer defaults to 0 (not -1) because the problem defines "no warmer day" as 0, matching its own stated default rather than the template's placeholder.
A monotonic stack is a pancake stack with a no-smaller-on-top rule — every time a bigger pancake arrives, it knocks off everything smaller beneath it, and each knock-off is exactly the answer for "what's the next bigger thing?"
A problem gives you a histogram (an array of bar heights) and asks for the area of the largest rectangle that fits under the histogram. Explain why you'd want, for each bar, the nearest shorter bar on both its left and right — and describe how running the monotonicStackTemplate skeleton with the comparison flipped to find "next smaller" would get you halfway there.