Pattern 20: Monotonic Stack

One-line trigger: “For each element, find the next / previous element that is greater / smaller.”

0. The Template (Copy-Paste Skeleton)

This is the only thing you need to memorise. Every monotonic-stack problem is this skeleton with two knobs changed: the comparison operator and the iteration direction.

// UNIVERSAL MONOTONIC STACK TEMPLATE
// Stack holds INDICES (not values) so you can compute distances.
int[] monotonicStack(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);                       // default = "nothing found"
    Deque<Integer> stack = new ArrayDeque<>();  // NEVER java.util.Stack

    for (int i = 0; i < n; i++) {               // KNOB 2: direction (see table)
        // KNOB 1: the comparison decides which of the 4 variants you get
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int idx = stack.pop();
            res[idx] = nums[i];                 // or (i - idx) for a distance answer
        }
        stack.push(i);
    }
    // Anything left in the stack has no answer → stays -1
    return res;
}

The two knobs — memorise this table, not four separate algorithms

You want	Iterate	Pop while	Stack ends up
Next Greater element	left → right	nums[stack.peek()] < nums[i]	decreasing
Next Smaller element	left → right	nums[stack.peek()] > nums[i]	increasing
Previous Greater element	left → right, answer = stack.peek() before push	pop while nums[peek] <= nums[i]	decreasing
Previous Smaller element	left → right, answer = stack.peek() before push	pop while nums[peek] >= nums[i]	increasing

Alternative for “previous X”: run the same “next X” loop right → left. Both are correct — pick one and stick with it so you never confuse yourself under interview pressure.

Circular-array variant (LC 503)

for (int i = 0; i < 2 * n; i++) {            // walk the array twice
    int cur = nums[i % n];
    while (!stack.isEmpty() && nums[stack.peek()] < cur) res[stack.pop()] = cur;
    if (i < n) stack.push(i);                // only push during the FIRST pass
}

Sentinel trick (histogram / trapping-rain problems)

Append a 0 (or Integer.MIN_VALUE) to the end of the input so the stack is guaranteed to drain — this removes the “leftover elements” cleanup loop entirely.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Next greater / next smaller / previous greater / previous smaller element”
• “How many days until a warmer temperature” → next greater, answer is a distance
• “Largest rectangle” in a histogram / in a binary matrix
• “Span” problems (stock span, sum of subarray minimums)
• “Remove k digits to make the smallest number” → greedy + monotonic stack
• Brute force is an obvious O(n²) double loop, and the constraint says n ≤ 10^5 → you need O(n)

The ‘Trick’ to Know

An element is popped exactly once. When element i pops element j, you have just discovered — in O(1) — the answer for j that a nested loop would have spent O(n) searching for. That amortisation is why the whole thing is O(n) despite the nested while.

The second insight: push indices, not values. Values give you “what”; indices give you “what” and “how far”, which is what half the problems actually ask for.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Daily Temperatures — LC 739

Given temps[], return answer[i] = number of days you must wait after day i for a warmer temperature. 0 if it never gets warmer.

Brute Force: nested scan — O(n²)

class Solution {
    public int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {      // scan forward for the first warmer day
                if (temps[j] > temps[i]) { res[i] = j - i; break; }
            }
        }
        return res;   // 73,74,75,71,69,72,76,73 → 1,1,4,2,1,1,0,0
    }
}

Why it’s slow: for a strictly decreasing input ([100, 99, 98, ...]) every inner loop runs to the end → 1+2+…+n = O(n²), ~10^10 ops at n = 10^5. TLE.

Optimal: Monotonic Decreasing Stack — O(n)

class Solution {
    public int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] res = new int[n];                       // default 0 = "never gets warmer"
        Deque<Integer> stack = new ArrayDeque<>();    // holds INDICES, temps decreasing

        for (int i = 0; i < n; i++) {
            // temps[i] is the NEXT GREATER for every colder index sitting on the stack
            while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
                int prev = stack.pop();
                res[prev] = i - prev;                 // distance, because we stored indices
            }
            stack.push(i);
        }
        return res;                                   // leftovers keep res = 0
    }
}

Java Architecture Insights

• ArrayDeque over java.util.Stack — Stack extends Vector, so every push/pop is synchronized (dead weight in single-threaded interview code) and it iterates bottom-to-top, which is the opposite of stack order. ArrayDeque is the officially recommended stack. Say this in the interview — it is a free senior signal.
• Deque<Integer> boxes every index. If the interviewer pushes on performance, offer int[] stack = new int[n]; int top = -1; — an array-backed stack with zero boxing. Mention it; only write it if asked.
• peek() vs pop() — ArrayDeque.peek() returns null on empty (no exception), so the !stack.isEmpty() guard must come first in the &&; short-circuit evaluation saves you from a NullPointerException on auto-unboxing.
• Arrays.fill(res, -1) when “not found” must be distinguishable from a real answer of 0.

---

3. Mental Model & Visualization

ASCII Trace — temps = [73, 74, 75, 71, 69, 72, 76, 73]

i=0 t=73   stack: []            push 0            stack(idx)=[0]        res=[0,0,0,0,0,0,0,0]
i=1 t=74   74 > temps[0]=73 → pop 0, res[0]=1-0=1
                                 push 1            stack=[1]            res=[1,0,...]
i=2 t=75   75 > temps[1]=74 → pop 1, res[1]=2-1=1
                                 push 2            stack=[2]            res=[1,1,...]
i=3 t=71   71 < 75            push 3               stack=[2,3]
i=4 t=69   69 < 71            push 4               stack=[2,3,4]
i=5 t=72   72 > temps[4]=69 → pop 4, res[4]=5-4=1
           72 > temps[3]=71 → pop 3, res[3]=5-3=2
           72 < temps[2]=75 → stop; push 5         stack=[2,5]
i=6 t=76   76 > temps[5]=72 → pop 5, res[5]=6-5=1
           76 > temps[2]=75 → pop 2, res[2]=6-2=4
                                 push 6            stack=[6]
i=7 t=73   73 < 76            push 7               stack=[6,7]

leftover [6,7] → never warmer → res[6]=res[7]=0
FINAL: [1, 1, 4, 2, 1, 1, 0, 0]

The stack as a “waiting room”

   Stack (top on the right) always holds a DECREASING wall of temperatures:

        75
        |‾‾|  71
        |  |  |‾|  69          ← everyone here is still WAITING for a warmer day
        |  |  | |  | |
        idx2  idx3  idx4

   A new hotter reading (72) walks in and evicts everyone shorter than it —
   each evictee gets their answer on the way out, in O(1).

Senior Mental Trigger

“‘Next/previous greater-or-smaller’ or an O(n²) double loop over a 10^5 array → push indices onto a monotonic stack; the popper is the answer.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty	Which knob
LC 496	Next Greater Element I	Easy	next greater + HashMap
LC 739	Daily Temperatures	Medium	next greater (distance)
LC 503	Next Greater Element II	Medium	next greater, circular (2n loop)
LC 901	Online Stock Span	Medium	previous greater (streaming)
LC 1019	Next Greater Node In Linked List	Medium	next greater on a list
LC 20	Valid Parentheses	Easy	plain stack warm-up

FAANG ‘Aha!’ Level (Hard / Unintuitive)

#	Problem	Difficulty	The twist
LC 84	Largest Rectangle in Histogram	Hard	width = i - stack.peek() - 1 after pop
LC 85	Maximal Rectangle	Hard	run LC 84 once per matrix row
LC 42	Trapping Rain Water	Hard	stack (or 2-pointer) — know both
LC 316	Remove Duplicate Letters	Hard	monotonic stack + “can I see it later?” check
LC 402	Remove K Digits	Medium	greedy increasing stack
LC 907	Sum of Subarray Minimums	Medium	count contributions via prev/next smaller
LC 1856	Maximum Subarray Min-Product	Medium	prev/next smaller + prefix sums
LC 2104	Sum of Subarray Ranges	Medium	two passes: max contribution − min contribution

The “counting contributions” family (LC 907, 1856, 2104)

These all reduce to: for each i, find left[i] = index of previous smaller and right[i] = index of next smaller. Then nums[i] is the minimum of exactly (i - left[i]) * (right[i] - i) subarrays. Handle duplicates by making one side strict and the other non-strict — otherwise you double-count. That asymmetry is the whole trick.

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Brute force double loop	O(n²)	O(1)	TLE past n ≈ 10^4
Monotonic stack	O(n)	O(n)	Each index pushed once, popped once → 2n ops amortised
Circular (2n pass)	O(n)	O(n)	Same bound; constant factor 2
LC 84 histogram	O(n)	O(n)	Sentinel bar avoids the drain loop
LC 85 maximal rectangle	O(rows·cols)	O(cols)	LC 84 per row on a running heights array

---

6. Common Variants & Extensions

• Monotonic Deque (sliding-window max, LC 239) — same discipline, but you also evict from the front when an index falls out of the window. That lives in 21-Stacks-And-Queues §Monotonic Deque.
• Two-pointer alternative — LC 42 has an O(1)-space two-pointer solution. When the interviewer says “can you do better on space?”, that is the expected answer.
• Stack + HashMap (LC 496) — precompute next-greater for nums2 into a map, then answer nums1 queries in O(1). Classic “decouple the computation from the query” move.
• Monotonic stack on a linked list (LC 1019) — convert to array first, or recurse and process on the way back up.

---

7. Interview Red Flags & Gotchas

• ❌ Pushing values instead of indices. You lose distance and width. Push indices; read nums[stack.peek()] when you need the value.
• ❌ isEmpty() check after the comparison. nums[stack.peek()] on an empty ArrayDeque NPEs on unboxing. Guard first.
• ❌ < vs <= chosen by feel. With duplicates these give different answers. Decide it deliberately: for contribution-counting use strict on one side, non-strict on the other.
• ❌ Forgetting the leftovers. Elements still on the stack at the end have no next greater — make sure the default value is right (-1 vs 0 vs n).
• ❌ Claiming O(n²) because of the nested while. Interviewers probe this. The answer: each of the n indices is pushed once and popped at most once, so total inner iterations ≤ n across the whole run — amortised O(1) per element.
• ❌ Using java.util.Stack. Works, but flags you as not current.

---

8. Companion 90-second Pitch (verbal)

“The brute force is, for every element, scan right until I find something bigger — O(n²). The observation is that when I’m scanning and I hit a bigger value, that value is the answer for several pending elements at once, not just one. So I keep a stack of indices whose answer is still unknown, and I maintain it in decreasing order of value. When a new element arrives, everything on the stack smaller than it gets popped, and each popped index’s answer is this new element — or i - poppedIndex if the question asks for a distance. Every index is pushed once and popped once, so it’s O(n) time, O(n) space. I use ArrayDeque rather than java.util.Stack because Stack is a synchronized Vector and iterates in the wrong order. Anything still on the stack at the end has no answer, so it keeps the default.”