/Projects
Coding patterns · 06 of 15

Monotonic stack

Keep a stack in sorted order to find the next greater or smaller.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot monotonic stack from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(n) time, O(n) space Watch as reels
Part 1 of 5

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.

Why it works

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.

Next greater / smaller elementDays until a warmer temperatureLargest rectangle in a histogramRemove digits to make the smallest number
Part 2 of 5

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.

Problem

For each day, how many days until a warmer temperature? 0 if none.

Plan before you code

  1. Same template, but store the distance instead of the value.
Part 3 of 5

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

next-greater-element.tsTypeScript
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}
11 linesUTF-8TypeScript
  1. The stack holds indices still waiting for an answer.
  2. A bigger value resolves every smaller one on the stack.
  3. The current index now waits for its own answer.

3.2Solution

Strict TypeScript, type-checked and tested.

Daily Temperatures

daily-temperatures.tsTypeScript
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}
12 linesUTF-8TypeScript

Step by step

  1. Answers default to 0; the stack holds days still waiting.
  2. A warmer day answers every colder day waiting on the stack.
  3. Today waits for its own warmer day.

Complexity: O(n) time, O(n) space

Part 4 of 5

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?
For 'next greater', keep a decreasing stack; for 'next smaller', an increasing one. Ask what event resolves a waiting element.
Why store indices instead of values?
An index gives you the value and the distance, which many answers need: days to wait, or the width of a rectangle.
Where else does this appear?
Stock spans, the largest rectangle in a histogram, trapping rain water, and removing digits to make the smallest number.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyNext Greater Element I
Hint

Run the template once, store results in a map.

MediumOnline Stock Span
Hint

Stack of (price, span); merge spans when popping.

Part 5 of 5

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
Hard

Largest Rectangle in Histogram

Find the area of the largest rectangle in a histogram.

  1. Keep bars in increasing height on a stack.
  2. When a shorter bar arrives, each popped bar's rectangle ends here and starts after the new stack top.
  3. A zero-height sentinel flushes the stack at the end.
largest-rectangle-histogram.tsTypeScript
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}
14 linesUTF-8TypeScript

Complexity: O(n) time, O(n) space

Medium

Remove K Digits

Remove k digits from a number string to make it as small as possible.

  1. A bigger digit before a smaller one should go: it makes the number larger.
  2. Keep a non-decreasing stack of digits.
  3. Trim leftover removals from the end and strip leading zeros.
remove-k-digits.tsTypeScript
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}
12 linesUTF-8TypeScript

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
AI Engineer · Monotonic stack