Monotonic stack

How does Monotonic stack work?

The stack holds indices, not values. Each index waits there for its answer.

Monotonic means the values at the stacked indices only move one way. For next greater, they never rise from bottom to top.

Before pushing a new index, pop every index the new value beats. Each pop is an answer.

The comparison decides what you get. Pop while the top is smaller for next greater.

Flip the comparison to pop while the top is bigger. That gives next smaller.

For the previous greater element, pop while the top's value is not bigger. The index left on top is the answer, and an empty stack means none.

Whatever survives on the stack never found an answer. Those slots keep the default.

The inner loop looks quadratic. Each index is pushed once and popped once, so the total is linear.

Sources: Wikipedia: All nearest smaller values

1. [0]Push index 0. Value 2 sits on the stack.
2. [0, 1]Value 1 loses to 2. Nothing pops, push index 1.
3. [2]Value 5 beats 1, then 2. Both pop, both answer 5.
4. [2, 3]Value 3 loses to 5. Push index 3.
5. [2, 3]Input ends. Indices 2 and 3 keep -1.

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

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

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

function nextGreater(array $nums): array {
    $result = array_fill(0, count($nums), -1);
    $stack = [];
    foreach ($nums as $i => $x) {
        while ($stack && $nums[end($stack)] < $x) {
            $result[array_pop($stack)] = $x;
        }
        $stack[] = $i;
    }
    return $result;
}

    public static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }

    public static int[] NextGreater(int[] nums) {
        var result = new int[nums.Length];
        Array.Fill(result, -1);
        var stack = new Stack<int>();
        for (int i = 0; i < nums.Length; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
                result[stack.Pop()] = nums[i];
            }
            stack.Push(i);
        }
        return result;
    }

A worked example of Monotonic stack

Daily temperatures

You get a list of daily temperatures. For each day, count the days until a warmer one.

No warmer day means 0. Nested loops run in O(n squared) and time out at 100000 days.

Daily temperatures is next greater element, with a distance instead of a value.

Walk left to right. Pop every day on the stack that is colder than today.

Today is that day's first warmer one. The wait is the gap between the indices.

Days left on the stack never warmed up. They keep their 0.

function dailyTemperatures(temps) {
    const wait = new Array(temps.length).fill(0);
    const stack = []; // indices, warmest at the bottom

    for (let today = 0; today < temps.length; today++) {
        while (
            stack.length &&
            temps[stack[stack.length - 1]] < temps[today]
        ) {
            const colder = stack.pop();
            wait[colder] = today - colder;
        }
        stack.push(today);
    }

    return wait; // days still on the stack keep their 0
}

When should you use Monotonic stack?

Use Monotonic stack when the problem statement says “next greater / next smaller element”, “daily temperatures until it gets warmer” or “largest rectangle in a histogram”. A solution built on it usually runs in O(n).

• •next greater / next smaller element
• •daily temperatures until it gets warmer
• •largest rectangle in a histogram
• •trap rainwater between bars
• •span/streak that ends at the first bigger or smaller value

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Monotonic stack confused with?

Monotonic stack is most often confused with Stack, Monotonic deque, Sliding window (variable), Binary heap and Sorting with a comparator.

• Stack: A plain stack pops when you say so. A monotonic stack pops on a comparison.
• Monotonic deque: A deque also drops elements that fall out of a window. With no expiry by age, a stack is enough.
• Sliding window (variable): A window answers questions about a range. This stack answers about one boundary element per index.
• Binary heap: A heap gives the global maximum in O(log n). The stack gives the nearest bigger neighbour in O(1).
• Sorting with a comparator: Sorting throws away positions. Next greater questions are entirely about position.

Common mistakes with Monotonic stack

• Pushing values instead of indices

  You need the position to compute a distance. Push the index, read the value with temps[i].

• Getting the comparison backwards

  Smaller on top gives next greater. Bigger on top gives next smaller.

• Forgetting the leftovers

  Elements still on the stack found no answer. Decide their value up front: -1, 0, or the length.

• Mishandling equal values

  Strict < keeps duplicates on the stack, <= pops them. Test [2, 2, 2] before you trust it.

Which interview problems use Monotonic stack?

Interview problems solved with Monotonic stack include Next greater element, Daily temperatures, Largest rectangle in a histogram, Trapping rain water, Stock span, Remove k digits and Sum of subarray minimums.

• Next greater element: The pattern with nothing hidden. Everything else is a rewording.
• Daily temperatures: Next greater, but it asks for the distance.
• Largest rectangle in a histogram: Each bar needs its first shorter neighbour on both sides.
• Trapping rain water: Water sits between a bar and the next taller one.
• Stock span: Next greater run backwards, counting days instead of values.
• Remove k digits: Pop bigger digits to leave the smallest number.
• Sum of subarray minimums: Each value owns a span bounded by smaller neighbours.

What is the time and space complexity of Monotonic stack?

The target complexity of Monotonic stack is O(n).

n up to 1e5 elements gives O(n). Each element is pushed once and popped at most once.