← System Design Simulator

Monotonic Stack Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated · Category: Stacks & Queues

Next greater element in O(n); each index pushed/popped once.

Concept

A monotonic stack is a stack that you deliberately keep sorted, either strictly increasing or strictly decreasing, by popping whatever violates the invariant before each push. This tiny discipline turns a category of seemingly-quadratic problems into linear ones. Next greater element, next smaller element, largest rectangle in a histogram, trapping rainwater, stock span, and daily temperatures are all the same algorithm dressed in different inputs. The reason it works is amortization: every element is pushed at most once and popped at most once across the entire run, so even though the inner while loop can pop many items in a single iteration, the total work across N iterations is O(N). Once you see the pattern, you stop reaching for nested loops and start reaching for a stack plus a running invariant.

Monotonic Stack — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Monotonic Stack visualization — animated algorithm, step-through, and live data-structure updates.

How it works

For next greater element on an array, iterate left to right and keep a stack of indices whose answer has not yet been resolved. At each index i, while the stack is non-empty and arr[stack.peek()] is strictly less than arr[i], pop that index and record answer[popped] = arr[i]. Then push i. Anything left on the stack at the end has no next greater element, so you fill those slots with -1 or any sentinel you prefer. The stack is strictly decreasing by value when you read it from bottom to top, which is exactly what makes it a monotonic stack. For the circular variant, iterate for 2N steps and take the index modulo N. For next smaller, flip the comparator. For largest rectangle in a histogram, push indices of bars in increasing order; when you see a bar shorter than the top, pop and compute the area using the popped bar's height and the index gap between the new stack top and i. The payoff is that each element is touched a constant number of times, so the total work is O(N) time and O(N) space for the stack and the answer array.

Implementation

Next greater element with a monotonic stack
import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.Deque;

public class MonotonicStack {
    /**
     * For each index i, return the next element to the right that is strictly greater,
     * or -1 if none. Stack holds indices whose answer is still pending and whose values
     * are strictly decreasing from bottom to top.
     */
    public static int[] nextGreaterElements(int[] arr) {
        int n = arr.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                int idx = stack.pop();
                answer[idx] = arr[i];
            }
            stack.push(i);
        }
        return answer;
    }

    /** Circular variant: treat the array as wrapping around. Iterate 2N times. */
    public static int[] nextGreaterCircular(int[] arr) {
        int n = arr.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int step = 0; step < 2 * n; step++) {
            int i = step % n;
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                answer[stack.pop()] = arr[i];
            }
            if (step < n) stack.push(i);
        }
        return answer;
    }

    /** Largest rectangle in histogram in O(N) using a monotonic increasing stack. */
    public static int largestRectangle(int[] heights) {
        int n = heights.length, best = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!st.isEmpty() && heights[st.peek()] > h) {
                int top = st.pop();
                int left = st.isEmpty() ? -1 : st.peek();
                best = Math.max(best, heights[top] * (i - left - 1));
            }
            st.push(i);
        }
        return best;
    }
}

Complexity

Common pitfalls

Key design decisions & trade-offs

Practice problems

Interview follow-ups

Why it matters

Monotonic Stack is a core part of the Stacks & Queues toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related