Monotonic Stack

Overview

A monotonic stack keeps elements in strictly increasing or strictly decreasing order (by value or by index). It answers "next greater element" or "next smaller element" for each index in O(n). You scan the array; when the current element violates the stack order, you pop until the invariant holds. Each pop gets its "next greater" (or "next smaller") from the current element.

Invariants: For next greater (scan left to right): stack holds indices with values in decreasing order (bottom to top). For next smaller: stack holds indices with values in increasing order.

When to Use

• Next greater / next smaller element for each index.
• Largest rectangle in histogram — previous and next smaller bar per index.
• Daily temperatures — days until warmer.
• Remove K digits — keep digits in increasing order.

How It Works (Next Greater)

Scan left to right. Stack = indices that do not yet have a next greater. For each i: while stack non-empty and arr[top] < arr[i], pop top — its next greater is arr[i] at i. Then push i. Stack stays decreasing by value (bottom to top).

Example 1: Next Greater Element

function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Time: O(n). Space: O(n).

Example 2: Next Smaller Element

Stack stays increasing (bottom to top). Pop when arr[top] > arr[i]; then current index i is the "next smaller" for the popped index.

function nextSmallerElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Example 3: Previous Greater Element

Scan left to right; when you pop, the top (before popping) is the "previous greater" for the current index i (the element to the left that is greater than arr[i]). Alternatively, assign to result[i] when you pop: the popped index’s previous greater is the new top (or -1). Common: for each i, find the nearest index j < i with arr[j] > arr[i]. Pop until top has value > arr[i]; then that top is the previous greater for i; push i.

function previousGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) stack.pop();
    if (stack.length > 0) result[i] = nums[stack[stack.length - 1]];
    stack.push(i);
  }
  return result;
}

Example 4: Daily Temperatures (Distance to Next Greater)

Same as next greater, but store index difference (i - j) instead of the value. Result[j] = i - j when arr[i] is the next greater for j.

function dailyTemperatures(temps: number[]): number[] {
  const result = new Array(temps.length).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop()!;
      result[j] = i - j;
    }
    stack.push(i);
  }
  return result;
}

Example 5: Next Greater Element II (Circular)

Each element can look to the right and then wrap to the start. Run the same monotonic stack over indices 0..2n-1 with value arr[i % n]. When i ≥ n, only assign result for indices that have not been set (e.g. result[j] only when j < n). Simpler: iterate i from 0 to 2*n-1, use idx = i % n; when you pop j, set result[j] = arr[idx] only once (e.g. when j < n and result[j] still -1), or always assign and let the second pass overwrite with the same value.

function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < 2 * n; i++) {
    const idx = i % n;
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[idx]) {
      result[stack.pop()!] = nums[idx];
    }
    if (i < n) stack.push(i);
  }
  return result;
}

Summary

• Monotonic stack: maintain order by popping until invariant holds; pops get next-greater or next-smaller from current index.
• Decreasing stack → next greater. Increasing stack → next smaller. See Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram.