Coding Patterns

Monotonic Stack and Monotonic Queue Explained

A monotonic stack or queue keeps values in increasing or decreasing order so we can answer next-greater, next-smaller, or sliding-window max/min questions efficiently.

StackQueueDequeCoding PatternArrays

The Short Answer

A monotonic stack or monotonic queue is a data structure that keeps elements in sorted order as you scan through an array.

The word monotonic means the values move in one direction: either increasing or decreasing.

The big idea: when a new value arrives, some older values become useless forever. We remove them immediately.

Why This Pattern Exists

Many array problems ask something like: “For each element, find the next greater value,” or “For every window of size k, find the maximum.”

The brute force solution often checks many elements again and again. A monotonic structure avoids that by keeping only the candidates that can still matter.

Brute Force

Repeated scanning

Check many future values repeatedly.

Monotonic Structure

Keep useful candidates only

Remove values that can no longer be the answer.

Monotonic Stack: Next Greater Element

Use a monotonic decreasing stack when the problem asks for:

next greater element
previous greater element
next smaller element
previous smaller element

The stack is called monotonic decreasing because values inside the stack decrease from bottom to top.

Decreasing stack

Each value is smaller than the one before it.

While scanning the input array left to right:

if the new element is smaller, push it onto the stack
if the new element is greater than the stack top, then the new element becomes the next greater element for one or more items already waiting in the stack
keep popping smaller elements until the stack becomes decreasing again

The key insight:

Once a larger element arrives, smaller elements behind it can never become the next greater element for future values. They are no longer useful and can be removed immediately.

Example input:

java

nums = [2, 1, 3, 2, 4]

Step-by-step intuition:

java

stack = []

            2 arrives
            stack = [2]

            1 arrives
            1 < 2
            push
            stack = [2, 1]

            3 arrives
            3 > 1 -> pop 1
            3 > 2 -> pop 2

            3 is the next greater element
            for both 1 and 2

            push 3
            stack = [3]

The stack stores elements whose next greater value has not yet been found.

java

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);

    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int index = stack.pop();
            result[index] = nums[i];
        }

        stack.push(i);
    }

    return result;
}

Monotonic Queue: Sliding Window Maximum

Use a monotonic queue when the question involves a moving window and you need the max or min inside that window.

Example:

java

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (window size)

Sliding windows:

java

There are 6 windows: nums.length - k + 1

[ 1,  3, -1]  -> max = 3
[ 3, -1, -3]  -> max = 3
[-1, -3,  5]  -> max = 5
[-3,  5,  3]  -> max = 5
[ 5,  3,  6]  -> max = 6
[ 3,  6,  7]  -> max = 7

Sliding window maximum:

java

result = [3, 3, 5, 5, 6, 7]

Queue intuition

front = max

remove expired

pop smaller from back

The front of the deque always holds the best candidate for the current window.

The deque stores indexes. The front is the current maximum. When the window moves, expired indexes leave from the front. When a larger value arrives, smaller values leave from the back.

java

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];

    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }

        while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

Stack vs Queue: How to Choose

Use Monotonic Stack

Next greater element
Next smaller element
Previous greater/smaller
Histogram boundaries
Temperature / stock span style problems

Use Monotonic Queue

Sliding window maximum
Sliding window minimum
Window with best candidate
Range max/min while moving left to right

Four Good Practice Problems

Monotonic Stack

Daily Temperatures

For each day, find how many days until a warmer temperature. This is a next-greater-element problem.

Monotonic Stack

Largest Rectangle in Histogram

Use previous/next smaller boundaries to calculate the best rectangle area for each bar.

Monotonic Queue

Sliding Window Maximum

For every window of size k, return the maximum value using a decreasing deque.

Monotonic Queue

Shortest Subarray with Sum at Least K

A harder prefix-sum + monotonic deque problem. Great once sliding window maximum makes sense.

The Interview-Friendly Explanation

A monotonic stack or queue keeps elements in increasing or decreasing order so we can discard values that can no longer become the answer. This usually turns an O(n²) brute-force scan into an O(n) solution because each element is added once and removed once.