When to use. For each index, the nearest previous/next value that is larger or smaller.
Complexity. Time O(n) — each index is pushed and popped at most once. Space O(n) for the stack.
Who gets asked. Rare as a named intern topic. Mid/senior loops expect you to reach for it on “next greater” shapes.
Prereq. Stacks; arrays.
Monotonic Stack
A stack that stays increasing or decreasing. When a new value would break the order, pop until it would not — those pops are exactly the “next greater / next smaller” answers.
The idea
Next greater to the right: walk left → right, keep a decreasing stack of indices. When nums[i] is bigger than the top, that top’s next greater is nums[i]. Push i.
Each index is pushed once and popped once, so O(n). The intern trap is a nested scan that is O(n²).
Histogram-largest-rectangle and “span of consecutive lesser days” are the same skeleton. If the prompt says nearest previous/next that is larger or smaller, start drawing a stack.
Worked example
Days until a warmer value
A list of daily highs. For each day, how many days until a strictly warmer high? 0 if none. Example: [17, 16, 19] → [2, 1, 0].
Walk i from 0 to n−1 with a stack of indices whose answer is still unknown, kept decreasing in temperature.
While the stack is not empty and today is warmer than temps[stack.top], pop and write i − that index.
Push i. Leftovers at the end stay 0.
function daysUntilWarmer(temps) {
const n = temps.length;
const answer = Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
Time O(n). Space O(n) for the stack in the worst case.
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Next greater copy
For each value, the next strictly larger value to its right, or −1. Linear time required.
Aim: O(n) time and space
Widest rectangle in a skyline
An array of bar heights. Largest area rectangle that fits under the skyline (bars are width 1).
Aim: O(n) with a monotonic stack of indices
Previous smaller
For each index, the nearest left index with a strictly smaller value. Foundation for histogram and rainwater variants.