Monotonic Stack: The Pattern Behind Next Greater Element and Daily Temperatures

The trigger: 'next greater' and 'next smaller' problems

A monotonic stack is the answer to a very specific question shape: for each element, find the next (or previous) element that is greater than it, or smaller than it. The canonical version is Next Greater Element — given an array, for every position return the first value to its right that is larger, or -1 if there is none.

The brute force is obvious and quadratic: for every element, walk right until you find something bigger. That is O(n²), and for a sorted-descending array it does the full n² work. The monotonic stack does the same job in O(n) by keeping a stack of elements that are still waiting for their next greater value, and resolving them the instant that value shows up.

Why it is O(n): the pushed-once, popped-once argument

The inner while loop that pops the stack looks like it could make the whole thing quadratic — a loop inside a loop. It does not, and the reason is the heart of the pattern. Across the entire scan, every index is pushed onto the stack exactly once, and once it is popped it never returns. So the total number of pops over the whole run is at most n, no matter how the array is shaped.

That is the amortized argument interviewers want to hear: the inner loop can pop several elements on one step, but those pops are "paid for" by the single push that put each element there. n pushes and at most n pops means O(n) total, even though a single step can do a lot of work.

This is also the sentence that separates a strong candidate from a memorizer. A memorizer says "it is a stack that stays sorted". A strong candidate says "the stack holds indices still waiting for their next greater element; a new value pops exactly the ones it resolves; each index is pushed and popped once, so it is linear". Same code, completely different level of understanding.

The universal template

Almost every monotonic stack solution is this exact shape. What changes between problems is tiny: the comparison direction (greater vs smaller), whether you store indices or values, and what you record when you pop. The scan-and-pop skeleton never changes.

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];              // holds INDICES, values kept decreasing

  for (let i = 0; i < nums.length; i++) {
    // current value resolves every smaller index waiting on top
    while (stack.length &&
           nums[i] > nums[stack[stack.length - 1]]) {
      const t = stack.pop();     // t was waiting; its answer is nums[i]
      res[t] = nums[i];
    }
    stack.push(i);               // i now waits for ITS next greater
  }
  return res;                    // whatever stays unresolved keeps -1
}

Increasing vs decreasing: which stack do you need?

This is the one decision that trips everyone up, and it flips based on a single word in the problem. The direction of the stack is opposite to the direction of what you are looking for, which feels backwards until you say it out loud a few times.

The mnemonic that sticks: you pop when you have found the answer. If you want the next greater element, the answer arrives when a bigger value shows up, so you pop on "greater", which leaves a decreasing stack behind. Flip the comparison to < and the exact same skeleton finds next-smaller instead. Previous-greater / previous-smaller is the same again, just read the stack top before you push instead of popping.

Pattern in the wild: Daily Temperatures (LC 739)

Daily Temperatures is the same algorithm with one change: instead of recording the next greater value, you record the distance to it. Given daily temperatures, for each day output how many days you wait for a warmer one. Because the stack holds indices, the gap is just i - t.

function dailyTemperatures(temps) {
  const res = new Array(temps.length).fill(0);
  const stack = [];              // indices of days awaiting a warmer day

  for (let i = 0; i < temps.length; i++) {
    while (stack.length &&
           temps[i] > temps[stack[stack.length - 1]]) {
      const t = stack.pop();
      res[t] = i - t;            // days until warmer = the index gap
    }
    stack.push(i);
  }
  return res;
}

Pattern in the wild: Largest Rectangle in Histogram (LC 84)

This is the problem that makes the monotonic stack feel like a superpower. For each bar, the widest rectangle it can anchor extends until it hits a shorter bar on either side. An increasing stack finds exactly those boundaries: when a bar is shorter than the stack top, that top's rectangle is now closed, and the width is the gap between the new boundary and the element below it on the stack.

function largestRectangle(heights) {
  const stack = [];              // indices, heights increasing
  let best = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    // a shorter bar closes every taller rectangle on the stack
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      const top = stack.pop();
      const height = heights[top];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

Common mistakes and edge cases

What interviewers actually look for

The monotonic stack is a favorite interview pattern precisely because the brute force is so obvious. Anyone can write the O(n²) double loop. The signal the interviewer is watching for is whether you recognize the "next greater / next smaller" shape and reach for the stack, then explain the amortized O(n) correctly.

Say the invariant out loud before you code: "I will keep a stack of indices whose next greater element I have not found yet. When a bigger value arrives, it resolves everything smaller on top." That single sentence tells the interviewer you understand the data structure, not just the syntax, and it makes the code almost write itself.

Then defend the complexity: "The inner while loop looks quadratic, but each index is pushed once and popped once across the whole scan, so it is O(n) amortized." Naming the pushed-once, popped-once argument is the difference between reciting a solution and demonstrating that you actually understand why it is fast.

Frequently asked questions