Monotonic stack

Overview

A monotonic stack keeps its elements in increasing or decreasing order. Before pushing a new element, you pop every element that breaks the order. The moment an element is popped is exactly when you discover its next greater (or smaller) element: the one that caused the pop.

This turns 'for each element, find the next larger element' from O(n^2) into O(n), because each element is pushed once and popped at most once. It is the key to daily temperatures, stock span, largest rectangle in a histogram, and trapping rain water.

When to use it

• For each element, find the next or previous greater or smaller element.
• How far can each element extend left or right before a larger / smaller value blocks it.
• Sum or count over all subarrays of their minimum or maximum.
• Build the lexicographically smallest result by removing characters or digits.

Problem patterns it solves

Where it is used in real software

Key terms

Monotonic decreasing stack

Values decrease from bottom to top; used for next greater element.

Monotonic increasing stack

Values increase from bottom to top; used for next smaller element and histogram areas.

Store indexes

Push indexes so you can compute distances and look up values.

Sentinel

A final 0 or infinity pushed at the end to flush the remaining elements.

How it works, step by step

1. 1
   Pick the order

   Next greater: keep a decreasing stack. Next smaller: keep an increasing stack.

2. 2
   For each index i

   While the stack is not empty and nums[i] breaks the order with nums[top], pop top.

3. 3
   Record the answer for the popped index

   nums[i] is the next greater (or smaller) element of top; distance is i - top.

4. 4
   Push i

   i waits on the stack until something larger arrives.

5. 5
   Leftover indexes

   Elements still on the stack have no next greater element: answer -1 or 0.

Daily temperatures trace

temps = [73, 74, 75, 71, 69, 72, 76, 73]

answer = [1, 1, 4, 2, 1, 1, 0, 0]. Indexes 6 and 7 remain on the stack with no warmer day, so they stay 0.

Implementation

1function dailyTemperatures(temps) {2  const answer = new Array(temps.length).fill(0);3  const stack = []; // indexes, temperatures decreasing4  for (let i = 0; i < temps.length; i++) {5    while (stack.length && temps[i] > temps[stack.at(-1)]) {6      const j = stack.pop();7      answer[j] = i - j;8    }9    stack.push(i);10  }11  return answer;12}13 14function largestRectangleArea(heights) {15  const stack = []; // indexes, heights increasing16  let best = 0;17  for (let i = 0; i <= heights.length; i++) {18    const h = i === heights.length ? 0 : heights[i]; // sentinel flushes the stack19    while (stack.length && heights[stack.at(-1)] > h) {20      const height = heights[stack.pop()];21      const left = stack.length ? stack.at(-1) + 1 : 0;22      best = Math.max(best, height * (i - left));23    }24    stack.push(i);25  }26  return best;27}28 29// 402. Remove K Digits: keep an increasing stack of digits30function removeKdigits(num, k) {31  const stack = [];32  for (const d of num) {33    while (k > 0 && stack.length && stack.at(-1) > d) {34      stack.pop();35      k--;36    }37    stack.push(d);38  }39  stack.length -= k; // remove the rest from the end40  const result = stack.join("").replace(/^0+/, "");41  return result || "0";42}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Pushing values instead of indexes.

  Fix: Indexes give distances and widths; values alone do not.

• Forgetting leftover elements.

  Fix: Use a sentinel or handle the remaining stack after the loop.

• Wrong width in histogram.

  Fix: Width = i - (new top + 1), or i when the stack becomes empty.

• Double counting with duplicates.

  Fix: Make one side strict and the other non-strict.

Interview questions

Practice problems