Monotonic Stack: Next Greater Element and Histogram

Some questions ask the same thing about every element of an array: what is the first larger number to its right? How many days until a warmer one? What is the nearest smaller value to its left? Answering each separately costs O(n²) in all. A monotonic stack answers all of them in one pass, and pushed a little further it solves a classic hard problem: the largest rectangle in a histogram.

A monotonic stack is an ordinary stack with one rule: its values are always sorted, increasing or decreasing from bottom to top.

Why checking every pair is too slow

Take the next greater element: for each position, the first value to its right that is larger, or −1. The brute force scans right from every position until something larger appears. On a decreasing array no scan ever succeeds, so the inner loops run about n²/2 times — 5 × 10⁹ comparisons for n = 100,000. The waste is re-reading: when the scan for 3 passes a 1 and a 2 to reach a 7, it has learnt that 7 answers the 1 and the 2 as well, and throws that knowledge away.

The idea: a stack that stays sorted

Turn the question round: scan left to right once and let each new element answer the earlier ones still waiting, kept on a stack of indices. When a new value arrives:

• Pop every waiting index whose value is smaller, and record the new value as its answer.
• Push the new index; it now waits for something larger.
• At the end, whatever is still on the stack never met a larger value: its answer is −1.

1. For each number, find the first larger number to its right. A stack holds the indices still waiting for an answer; their values only decrease from bottom to top, because a larger arrival would already have answered any smaller one below it.
2. 2 at index 0 has nothing before it to answer, so index 0 is simply pushed to wait for something larger.
3. 1 at index 1 is not larger than 2 on top, so it answers nobody and is pushed to wait too. The waiting values [2, 1] still decrease from bottom to top.
4. 5 at index 2 is larger than 1 and 2 on the stack, so 5 is the next greater element for each of them, and they are popped. The stack is now empty, so index 2 is pushed.
5. 6 at index 3 is larger than 5 on the stack, so 6 is the next greater element for 5, which is popped. The stack is now empty, so index 3 is pushed.
6. 2 at index 4 is not larger than 6 on top, so it answers nobody and is pushed to wait too. The waiting values [6, 2] still decrease from bottom to top.
7. 3 at index 5 is larger than 2 on the stack, so 3 is the next greater element for 2, which is popped. 6 is larger than 3, so popping stops there and index 5 is pushed.
8. Indices 3 and 5 (values 6 and 3) never met a larger number, so their answer is -1: the result is [5, 5, 6, -1, 3, -1]. Each index was pushed once and popped at most once, so the scan is O(n), not the O(n²) of checking every pair.

The waiting values always decrease from bottom to top. Nobody enforces that separately: a value is only pushed after everything smaller has been popped, so it always lands on something at least as large. That is a monotonic decreasing stack.

Why it works

Each answer is right. When index i pops index j, nums[i] is greater and to the right. It is the first such value because every index between them arrived while j was waiting and did not pop it, so none of them was greater.

1. Draw the values as bars. When index i pops index j, the scan records nums[i] as j's next greater value. Why is it the first one? Look along a line at the height of bar j.
2. 3 at index 3 pops 1, its neighbour: nothing lies between them, so 3 is trivially the first greater value.
3. 3 at index 3 pops 2 (index 1). Every bar between them — 1 — arrived while 2 was waiting and did not pop it, so none was taller: 3 is the first value to rise above the line.
4. 6 at index 4 pops 3, its neighbour: nothing lies between them, so 6 is trivially the first greater value.
5. 6 at index 4 pops 5 (index 0). Every bar between them — 2, 1 and 3 — arrived while 5 was waiting and did not pop it, so none was taller: 6 is the first value to rise above the line.
6. 6 and 4 were never popped, so no later bar rose above them and −1 is right. Every answer, [6, 3, 3, 6, -1, -1], was fixed at the moment its index was popped and never looked at again.

Popping looks like throwing information away, and the general reason it is safe is domination: an element leaves the stack the moment a newer element makes it useless for every question still to come — here, because it has its answer.

It is O(n), despite the loop inside a loop. The inner loop only pops, and each index is pushed exactly once, so it can be popped at most once.

1. Every push and pop of the next-greater scan, stacked over the step that made it. Most steps do one push, but the step that reads 5 does 5 operations at once — which is what makes the inner loop look quadratic.
2. The same 15 operations regrouped by the index they were about. Each index is pushed exactly once and popped at most once, so no column holds more than two: at most 2n operations however they bunch up. A burst of pops only uses up pops that no later step can make — O(n) amortised.

The code

The stack stores indices, not values: an index gives the value and the distance, so one function answers both the next greater value and "how many days until a warmer one?", which is Daily Temperatures.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// For each index, the index of the first greater value to its right, or -1.
vector<int> nextGreaterIndex(const vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, -1);
    vector<int> stack;  // indices still waiting; their values decrease bottom to top
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && nums[stack.back()] < nums[i]) {
            answer[stack.back()] = i;  // nums[i] is the first greater value after it
            stack.pop_back();
        }
        stack.push_back(i);  // wait for something greater than nums[i]
    }
    return answer;  // indices never popped keep -1
}

void printRow(const string& label, const vector<int>& row) {
    cout << label;
    for (int x : row) cout << " " << x;
    cout << "\n";
}

int main() {
    vector<int> nums = {2, 1, 5, 6, 2, 3};
    vector<int> next = nextGreaterIndex(nums), values;
    for (int j : next) values.push_back(j == -1 ? -1 : nums[j]);
    printRow("nums:        ", nums);
    printRow("next greater:", values);

    vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> warmer = nextGreaterIndex(temps), waits;
    for (int i = 0; i < (int)temps.size(); i++) waits.push_back(warmer[i] == -1 ? 0 : warmer[i] - i);
    printRow("temperatures:", temps);
    printRow("days to wait:", waits);
    return 0;
}

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    // For each index, the index of the first greater value to its right, or -1.
    static int[] nextGreaterIndex(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>();  // indices still waiting; their values decrease bottom to top
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                answer[stack.pop()] = i;  // nums[i] is the first greater value after it
            }
            stack.push(i);  // wait for something greater than nums[i]
        }
        return answer;  // indices never popped keep -1
    }

    static void printRow(String label, int[] row) {
        StringBuilder line = new StringBuilder(label);
        for (int x : row) line.append(" ").append(x);
        System.out.println(line);
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 6, 2, 3};
        int[] next = nextGreaterIndex(nums);
        int[] values = new int[nums.length];
        for (int i = 0; i < nums.length; i++) values[i] = next[i] == -1 ? -1 : nums[next[i]];
        printRow("nums:        ", nums);
        printRow("next greater:", values);

        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] warmer = nextGreaterIndex(temps);
        int[] waits = new int[temps.length];
        for (int i = 0; i < temps.length; i++) waits[i] = warmer[i] == -1 ? 0 : warmer[i] - i;
        printRow("temperatures:", temps);
        printRow("days to wait:", waits);
    }
}

def next_greater_index(nums):
    """For each index, the index of the first greater value to its right, or -1."""
    answer = [-1] * len(nums)
    stack = []  # indices still waiting; their values decrease bottom to top
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            answer[stack.pop()] = i  # nums[i] is the first greater value after it
        stack.append(i)  # wait for something greater than nums[i]
    return answer  # indices never popped keep -1


def print_row(label, row):
    print(label, *row)


nums = [2, 1, 5, 6, 2, 3]
nxt = next_greater_index(nums)
print_row("nums:        ", nums)
print_row("next greater:", [-1 if j == -1 else nums[j] for j in nxt])

temps = [73, 74, 75, 71, 69, 72, 76, 73]
warmer = next_greater_index(temps)
print_row("temperatures:", temps)
print_row("days to wait:", [0 if j == -1 else j - i for i, j in enumerate(warmer)])

// For each index, the index of the first greater value to its right, or -1.
function nextGreaterIndex(nums) {
  const answer = new Array(nums.length).fill(-1);
  const stack = []; // indices still waiting; their values decrease bottom to top
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      answer[stack.pop()] = i; // nums[i] is the first greater value after it
    }
    stack.push(i); // wait for something greater than nums[i]
  }
  return answer; // indices never popped keep -1
}

function printRow(label, row) {
  console.log(label + " " + row.join(" "));
}

const nums = [2, 1, 5, 6, 2, 3];
const next = nextGreaterIndex(nums);
printRow("nums:        ", nums);
printRow("next greater:", next.map((j) => (j === -1 ? -1 : nums[j])));

const temps = [73, 74, 75, 71, 69, 72, 76, 73];
const warmer = nextGreaterIndex(temps);
printRow("temperatures:", temps);
printRow("days to wait:", warmer.map((j, i) => (j === -1 ? 0 : j - i)));

nums:         2 1 5 6 2 3
next greater: 5 5 6 -1 3 -1
temperatures: 73 74 75 71 69 72 76 73
days to wait: 1 1 4 2 1 1 0 0

Previous smaller element

The mirror question looks left: for each element, the nearest value before it that is smaller. You still scan left to right, but the answer for the current element is read from the top after popping, rather than handed to the popped ones.

1. For each element, the nearest value to its left that is smaller. Scan left to right; this time the answer for the current element is read from the stack, not handed to the popped ones.
2. 4 has nothing to its left, so its answer is −1; push it.
3. 4 on top is smaller than 5, so nothing is popped and 4 is the answer. Push 5: the stack, [4, 5], increases from bottom to top.
4. 2 pops 5 and 4: they are no smaller than 2 and further away, so for any later element 2 is always the better candidate — they are dominated and can go. The stack is empty, so the answer is −1.
5. 2 on top is smaller than 10, so nothing is popped and 2 is the answer. Push 10: the stack, [2, 10], increases from bottom to top.
6. 8 pops 10: it is no smaller than 8 and further away, so for any later element 8 is always the better candidate — it is dominated and can go. The top is now 2, the answer.
7. The answers are [-1, 4, -1, 2, 2]. Popping on >= keeps the stack strictly increasing, so its top is always the nearest smaller candidate. Each index is pushed once and popped at most once: O(n).

An element j can go once a later element i is no larger: i is nearer to everything still to come and at least as small, so j can never again be anyone's nearest smaller value. The same scan answers Nearest Smaller Element, and the Stock Span Problem is "previous greater" turned into a count of days.

Which order answers which question

The memory aid: to find greater elements keep the stack decreasing; to find smaller ones keep it increasing. With repeated values, decide whether an equal value counts before choosing between < and <=: Final Prices With a Special Discount in a Shop wants smaller or equal.

Largest rectangle in a histogram

Largest Rectangle in Histogram asks for the largest rectangle under bars of width 1. Trying every pair of edges is O(n²). The key observation: the best rectangle's height is its shortest bar, so for each bar find the widest rectangle in which it is the shortest — from just after the previous smaller bar to just before the next smaller one.

One increasing stack gives both boundaries at once: the bar that pops bar j is its right boundary, and the bar left on top is its left one. A height-0 sentinel at the end pops everything left.

1. The best rectangle's height is the height of its shortest bar. So for each bar, find the widest rectangle in which it is the shortest: it stretches left to the previous smaller bar and right to the next smaller one. An increasing stack finds both.
2. Bar 0 (height 2) is pushed. A bar waits on the stack until a shorter one arrives, because until then its rectangle can still grow to the right.
3. 1 at index 1 is not taller than 2 on top, so it pops it. That bar's rectangle ends just before index 1 and starts just after the left edge, since nothing is left below it: 2 × 1 = 2, the best so far. Then 1 is pushed.
4. 5 and 6 are each taller than the top, so nothing is popped and they are pushed: the heights on the stack, [1, 5, 6], still increase from bottom to top.
5. 2 at index 4 is not taller than 6 on top, so it pops it. That bar's rectangle ends just before index 4 and starts just after index 2, the bar now on top: 6 × 1 = 6, the best so far.
6. 2 at index 4 is not taller than 5 on top, so it pops it. That bar's rectangle ends just before index 4 and starts just after index 1, the bar now on top: 5 × 2 = 10, the best so far. Then 2 is pushed.
7. 3 is taller than the top, so nothing is popped and it is pushed: the heights on the stack, [1, 2, 3], still increase from bottom to top.
8. The height-0 sentinel at index 6 pops the bar of height 3. That bar's rectangle ends just before index 6 and starts just after index 4, the bar now on top: 3 × 1 = 3.
9. The height-0 sentinel at index 6 pops the bar of height 2. That bar's rectangle ends just before index 6 and starts just after index 1, the bar now on top: 2 × 4 = 8.
10. The height-0 sentinel at index 6 pops the bar of height 1. That bar's rectangle ends just before index 6 and starts just after the left edge, since nothing is left below it: 1 × 6 = 6.
11. Every bar was measured exactly once, when it was popped, so the whole scan is O(n). The largest rectangle has area 10: height 5 across indices 2 to 3.

With equal heights, the first of two equal bars is popped by the second and measured too narrow, but the second is popped later with the full width, so the maximum is unaffected.

The code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int largestRectangle(const vector<int>& heights) {
    int n = heights.size();
    vector<int> stack;  // indices of bars, heights increasing bottom to top
    int best = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];  // a height-0 bar at the end flushes the stack
        while (!stack.empty() && heights[stack.back()] >= h) {
            int bar = stack.back();
            stack.pop_back();
            int left = stack.empty() ? -1 : stack.back();  // the previous smaller bar
            int width = i - left - 1;                       // i is the next smaller (or equal) bar
            best = max(best, heights[bar] * width);
        }
        stack.push_back(i);
    }
    return best;
}

int main() {
    vector<vector<int>> tests = {{2, 1, 5, 6, 2, 3}, {2, 4}, {6, 2, 5, 4, 5, 1, 6}};
    for (const vector<int>& heights : tests) {
        cout << "heights";
        for (int h : heights) cout << " " << h;
        cout << " -> largest rectangle " << largestRectangle(heights) << "\n";
    }
    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static int largestRectangle(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();  // indices of bars, heights increasing bottom to top
        int best = 0;
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];  // a height-0 bar at the end flushes the stack
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int bar = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();  // the previous smaller bar
                int width = i - left - 1;                         // i is the next smaller (or equal) bar
                best = Math.max(best, heights[bar] * width);
            }
            stack.push(i);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] tests = {{2, 1, 5, 6, 2, 3}, {2, 4}, {6, 2, 5, 4, 5, 1, 6}};
        for (int[] heights : tests) {
            StringBuilder line = new StringBuilder("heights");
            for (int h : heights) line.append(" ").append(h);
            line.append(" -> largest rectangle ").append(largestRectangle(heights));
            System.out.println(line);
        }
    }
}

def largest_rectangle(heights):
    n = len(heights)
    stack = []  # indices of bars, heights increasing bottom to top
    best = 0
    for i in range(n + 1):
        h = 0 if i == n else heights[i]  # a height-0 bar at the end flushes the stack
        while stack and heights[stack[-1]] >= h:
            bar = stack.pop()
            left = stack[-1] if stack else -1  # the previous smaller bar
            width = i - left - 1               # i is the next smaller (or equal) bar
            best = max(best, heights[bar] * width)
        stack.append(i)
    return best


tests = [[2, 1, 5, 6, 2, 3], [2, 4], [6, 2, 5, 4, 5, 1, 6]]
for heights in tests:
    print("heights", *heights, "-> largest rectangle", largest_rectangle(heights))

function largestRectangle(heights) {
  const n = heights.length;
  const stack = []; // indices of bars, heights increasing bottom to top
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]; // a height-0 bar at the end flushes the stack
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= h) {
      const bar = stack.pop();
      const left = stack.length > 0 ? stack[stack.length - 1] : -1; // the previous smaller bar
      const width = i - left - 1; // i is the next smaller (or equal) bar
      best = Math.max(best, heights[bar] * width);
    }
    stack.push(i);
  }
  return best;
}

const tests = [[2, 1, 5, 6, 2, 3], [2, 4], [6, 2, 5, 4, 5, 1, 6]];
for (const heights of tests) {
  console.log(`heights ${heights.join(" ")} -> largest rectangle ${largestRectangle(heights)}`);
}

heights 2 1 5 6 2 3 -> largest rectangle 10
heights 2 4 -> largest rectangle 4
heights 6 2 5 4 5 1 6 -> largest rectangle 12

The same "how far does this element reach as the minimum?" question drives Sum of Subarray Minimums: element i is the minimum of (i − prevSmaller) × (nextSmaller − i) subarrays. Maximal Rectangle runs the histogram algorithm once per row of a binary matrix.

The monotonic deque: sliding window maximum

Sliding Window Maximum asks for the maximum of every window of k elements. Rescanning each window is O(n × k) and a heap is O(n log n); a monotonic deque — a queue that can also pop at the back — does it in O(n).

1. Every window of 3 needs its maximum. A deque holds indices whose values decrease from front to back, so the front is always the window's maximum; a value smaller than a newer one can never be a maximum again, so it is dropped from the back.
2. 1 enters the window at index 0. The window is not full yet.
3. 3 enters the window at index 1. 1 is no larger and will leave the window before 3 does, so it is dropped from the back. The window is not full yet.
4. -1 enters the window at index 2. It is smaller than 3, so it waits at the back in case the larger values slide out first. The front, 3, is the maximum of [1, 3, -1].
5. -3 enters the window at index 3. It is smaller than -1, so it waits at the back in case the larger values slide out first. The front, 3, is the maximum of [3, -1, -3].
6. 5 enters the window at index 4. Index 1 (3) has slid out of the window, so it leaves from the front. -3 and -1 are no larger and will leave the window before 5 does, so they are dropped from the back. The front, 5, is the maximum of [-1, -3, 5].
7. 3 enters the window at index 5. It is smaller than 5, so it waits at the back in case the larger values slide out first. The front, 5, is the maximum of [-3, 5, 3].
8. 6 enters the window at index 6. 3 and 5 are no larger and will leave the window before 6 does, so they are dropped from the back. The front, 6, is the maximum of [5, 3, 6].
9. 7 enters the window at index 7. 6 is no larger and will leave the window before 7 does, so it is dropped from the back. The front, 7, is the maximum of [3, 6, 7].
10. Every window has its maximum: [3, 3, 5, 5, 6, 7]. Each index joins the deque once and leaves at most once, from the front or the back, so the pass is O(n), where rescanning every window would be O(n·k).

The back is pruned by domination: an older value no larger than the newcomer leaves the window first and is never bigger while both are inside. The front is pruned by age. Each index enters and leaves once: O(n) time, O(k) space — the sliding window and the monotonic stack together.

Other shapes of the idea

• Circular arrays: in Next Greater Element II, scan the indices twice, reading nums[i % n], and push only during the first pass.
• Lookups for a subset: Next Greater Element I runs the scan once and keeps the answers in a hash map.
• Greedy removal: in Remove K Digits, keep digits in an increasing stack and pop a larger digit when a smaller one arrives, while removals are left.
• Contribution counting: Sum of Subarray Ranges counts how many subarrays each element is the minimum or maximum of.

Time and space complexity

How to recognise a monotonic stack problem

• For every element, the nearest element to its left or right that is greater or smaller: "next warmer", "how many days until", "span".
• A quantity limited by the smallest element in a range: rectangles under bars, subarray minimums.
• "Smallest number after removing k digits": greedy removal with an increasing stack.
• The maximum or minimum of every window: the monotonic deque.
• A brute force that reads "for each i, scan outwards until something bigger or smaller appears".

Common mistakes

• Storing values instead of indices: you lose distances, widths and which equal value is which.
• The wrong comparison for duplicates: < and <= give different answers when values repeat.
• Forgetting what is left on the stack: those indices still need an answer — or a sentinel to flush them.
• Choosing the wrong order: if the answers come out farthest rather than nearest, the order is backwards.
• Expiring the deque's front too late: remove it once its index is i - k or less, before reading the maximum.

Practice in this order

1. Final Prices With a Special Discount in a Shop: next smaller-or-equal, on a tiny array.
2. Nearest Smaller Element: previous smaller, read from the top.
3. Next Greater Element I: the core scan plus a hash map.
4. Daily Temperatures: the first program, answering with distances.
5. Stock Span Problem: previous greater, turned into a count.
6. Next Greater Element II: the same scan, circular.
7. Remove K Digits: an increasing stack used greedily.
8. Largest Rectangle in Histogram: both boundaries from one stack.
9. Sliding Window Maximum: the monotonic deque.

The monotonic stack problem list has every problem in the catalogue that uses it, and the monotonic queue list has the deque problems. This lesson closes the stacks stage; next on the road is Binary Search.