Monotonic Stack: The Next Greater Element Pattern

A monotonic stack is a stack whose elements are kept in sorted order (always increasing or always decreasing) as you push. Before pushing a new value, you pop everything that violates the order. This simple discipline solves a whole class of “find the next/previous greater or smaller element” problems in O(n) — replacing the obvious O(n²) double loop. It is one of the highest-leverage patterns in interviews.

The core problem: Next Greater Element

Given an array, for each element find the next element to its right that is larger; if none exists, report -1. Brute force scans right from every index: O(n²). The monotonic stack does it in one pass.

Key insight: scan left to right keeping a stack of indices whose answers are still unknown, with their values in decreasing order. When the current value is larger than the value at the top index, that current value is the “next greater” for the top — so pop it and record the answer. Repeat until the top is bigger, then push the current index.

#include <vector>
#include <stack>
std::vector<int> nextGreater(const std::vector<int>& a) {
    int n = a.size();
    std::vector<int> res(n, -1);
    std::stack<int> st;            // holds indices, values decreasing
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[i] > a[st.top()]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

import java.util.*;
int[] nextGreater(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> st = new ArrayDeque<>();   // indices, values decreasing
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && a[i] > a[st.peek()]) {
            res[st.pop()] = a[i];
        }
        st.push(i);
    }
    return res;
}

function nextGreater(a) {
  const n = a.length;
  const res = new Array(n).fill(-1);
  const st = [];                  // indices, values decreasing
  for (let i = 0; i < n; i++) {
    while (st.length && a[i] > a[st[st.length - 1]]) {
      res[st.pop()] = a[i];
    }
    st.push(i);
  }
  return res;
}

def next_greater(a):
    n = len(a)
    res = [-1] * n
    st = []                       # indices, values decreasing
    for i in range(n):
        while st and a[i] > a[st[-1]]:
            res[st.pop()] = a[i]
        st.append(i)
    return res

Complexity: O(n) time, O(n) space. Each index is pushed once and popped at most once — that’s the amortized O(n) argument, even though there’s a nested while.

Why O(n) despite a nested loop? Total pops across the whole run can’t exceed total pushes (n). The inner while does a lot of work occasionally, but never more than n times overall.

Reading the recipe

Memorize this skeleton; the four knobs are all you change per problem:

1. Iterate left→right (or right→left, depending on "next" vs "previous").
2. Keep a stack of INDICES.
3. While the new element breaks the desired order, pop and resolve those.
4. Push the new index.

Knobs:
 - direction (next vs previous)  → iterate forward vs backward
 - greater vs smaller            → flip the comparison (>  vs  <)
 - strict vs non-strict (> vs >=) → ties
 - store value or index/distance → what you record on pop

Variant: Daily Temperatures (distance, not value)

Same machinery, but record how many days until a warmer temperature — the index distance instead of the value.

#include <vector>
#include <stack>
std::vector<int> dailyTemperatures(const std::vector<int>& t) {
    int n = t.size();
    std::vector<int> res(n, 0);
    std::stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[i] > t[st.top()]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return res;
}

import java.util.*;
int[] dailyTemperatures(int[] t) {
    int n = t.length;
    int[] res = new int[n];        // defaults to 0
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && t[i] > t[st.peek()]) {
            int j = st.pop();
            res[j] = i - j;
        }
        st.push(i);
    }
    return res;
}

function dailyTemperatures(t) {
  const n = t.length;
  const res = new Array(n).fill(0);
  const st = [];
  for (let i = 0; i < n; i++) {
    while (st.length && t[i] > t[st[st.length - 1]]) {
      const j = st.pop();
      res[j] = i - j;
    }
    st.push(i);
  }
  return res;
}

def daily_temperatures(t):
    n = len(t)
    res = [0] * n
    st = []
    for i in range(n):
        while st and t[i] > t[st[-1]]:
            j = st.pop()
            res[j] = i - j
        st.append(i)
    return res

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

When to reach for a monotonic stack

The signal is: “for each element, find the nearest element to one side that is greater/smaller.” That covers Next/Previous Greater/Smaller Element, Daily Temperatures, Stock Span, Largest Rectangle in a Histogram, and Trapping Rain Water. Its sliding-window sibling, the monotonic deque, extends the idea to window max/min (see deque).

Pitfall: Mixing up indices and values on the stack. Store indices when you need distances or to index back into the array; store values only when the value alone is the answer. Pick one and stay consistent.

Ready to apply it? The stacks & queues exercises include monotonic-stack problems.