Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Keep indices on a stack whose values are decreasing. When a bigger value arrives, pop everything smaller: the new value is their 'next greater'. Each index is pushed and popped once.
The stack holds indices still waiting for an answer, with values decreasing from bottom to top. When a bigger value arrives, it is the first greater element for everything smaller on the stack, so those are popped and answered. Each index is pushed and popped once, so the scan is O(n).
Typical cost: O(n) time, O(n) space
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Daily Temperatures
The problem statement, then the plan you would say out loud.
For each day, how many days until a warmer temperature? 0 if none.
Plan before you code
- Same template, but store the distance instead of the value.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Next greater element to the right
1function nextGreater(nums: number[]): number[] {2 const res = new Array<number>(nums.length).fill(-1);3 const stack: number[] = []; // indices, values decreasing4 for (let i = 0; i < nums.length; i++) {5 while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {6 res[stack.pop()!] = nums[i];7 }8 stack.push(i);9 }10 return res;11}1fun nextGreater(nums: IntArray): IntArray {2 val res = IntArray(nums.size) { -1 }3 val stack = ArrayDeque<Int>() // indices, values decreasing4 for (i in nums.indices) {5 while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {6 res[stack.removeLast()] = nums[i]7 }8 stack.addLast(i)9 }10 return res11}1static int[] nextGreater(int[] nums) {2 int[] res = new int[nums.length];3 Arrays.fill(res, -1);4 Deque<Integer> stack = new ArrayDeque<>(); // indices, values decreasing5 for (int i = 0; i < nums.length; i++) {6 while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {7 res[stack.pop()] = nums[i];8 }9 stack.push(i);10 }11 return res;12}- The stack holds indices still waiting for an answer.
- A bigger value resolves every smaller one on the stack.
- The current index now waits for its own answer.
3.2Solution
Strict TypeScript, type-checked and tested.
Daily Temperatures
1function dailyTemperatures(t: number[]): number[] {2 const res = new Array<number>(t.length).fill(0);3 const stack: number[] = [];4 for (let i = 0; i < t.length; i++) {5 while (stack.length && t[stack[stack.length - 1]] < t[i]) {6 const j = stack.pop()!;7 res[j] = i - j;8 }9 stack.push(i);10 }11 return res;12}1fun dailyTemperatures(t: IntArray): IntArray {2 val res = IntArray(t.size)3 val stack = ArrayDeque<Int>()4 for (i in t.indices) {5 while (stack.isNotEmpty() && t[stack.last()] < t[i]) {6 val j = stack.removeLast()7 res[j] = i - j8 }9 stack.addLast(i)10 }11 return res12}1static int[] dailyTemperatures(int[] t) {2 int[] res = new int[t.length];3 Deque<Integer> stack = new ArrayDeque<>();4 for (int i = 0; i < t.length; i++) {5 while (!stack.isEmpty() && t[stack.peek()] < t[i]) {6 int j = stack.pop();7 res[j] = i - j;8 }9 stack.push(i);10 }11 return res;12}Step by step
- Answers default to 0; the stack holds days still waiting.
- A warmer day answers every colder day waiting on the stack.
- Today waits for its own warmer day.
Complexity: O(n) time, O(n) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Increasing or decreasing stack?
Why store indices instead of values?
Where else does this appear?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Run the template once, store results in a map.
Hint
Stack of (price, span); merge spans when popping.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Largest Rectangle in Histogram
Find the area of the largest rectangle in a histogram.
- Keep bars in increasing height on a stack.
- When a shorter bar arrives, each popped bar's rectangle ends here and starts after the new stack top.
- A zero-height sentinel flushes the stack at the end.
1function largestRectangle(heights: number[]): number {2 const stack: number[] = [];3 let best = 0;4 for (let i = 0; i <= heights.length; i++) {5 const h = i === heights.length ? 0 : heights[i]; // sentinel flushes the stack6 while (stack.length && heights[stack[stack.length - 1]] >= h) {7 const height = heights[stack.pop()!];8 const left = stack.length ? stack[stack.length - 1] + 1 : 0;9 best = Math.max(best, height * (i - left));10 }11 stack.push(i);12 }13 return best;14}Complexity: O(n) time, O(n) space
Remove K Digits
Remove k digits from a number string to make it as small as possible.
- A bigger digit before a smaller one should go: it makes the number larger.
- Keep a non-decreasing stack of digits.
- Trim leftover removals from the end and strip leading zeros.
1function removeKdigits(num: string, k: number): string {2 const stack: string[] = [];3 for (const d of num) {4 while (k > 0 && stack.length && stack[stack.length - 1] > d) {5 stack.pop();6 k--;7 }8 stack.push(d);9 }10 stack.length -= k;11 return stack.join("").replace(/^0+/, "") || "0";12}Complexity: O(n) time, O(n) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Storing values when you need indices
- Choosing < versus <= wrongly for duplicates