Monotonic Stack

A monotonic stack is a regular stack with a constraint — elements are always kept in sorted (monotonic) order, giving O(1) access to the nearest greater or smaller element at any point.

• Replaces O(n²) brute-force "next greater/smaller" scanning with O(n) — each element is pushed once and popped at most once across the entire loop
• Two variants: decreasing stack (pop when current is larger → answers "next greater element"), increasing stack (pop when current is smaller → answers "next smaller element")
• Reach for it when the problem involves "next greater/smaller", "how many days until", "span", "width of a range", or "area of a rectangle bounded by a histogram"

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of monotonic stack patterns.

Practice Tips

How to Identify a Monotonic Stack Problem

• "For each element, find the next element that is greater/smaller"
• "How many days/steps until a warmer/larger value?"
• "Largest rectangle/area" with bars of varying heights
• "Span" — how far back can you go while condition holds?
• Answer for each element depends on elements to its right (or left in reverse pass)

Monotonic Stack vs. Other Techniques

Interview Approach

1. Decide direction: are you looking for the next greater (decreasing stack) or next smaller (increasing stack)?
2. Store indices on the stack, not values — you need positions for distance and width calculations
3. Write the pop condition: pop while stack not empty AND nums[top] < current (decreasing) or > current (increasing)
4. Answer for the popped element goes into the result array at the popped index
5. After the loop, any indices left on the stack have no answer — leave them at the default (usually -1 or 0)

2 Main Patterns

Pattern 1: Monotonic Decreasing Stack (Next Greater Element)

Copy// Pop elements smaller than current — current is their "next greater"
Deque<Integer> stack = new ArrayDeque<>();   // stores indices
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        result[stack.pop()] = nums[i];       // nums[i] is the next greater
    }
    stack.push(i);
}
// Remaining indices on stack have no next greater → leave at default (-1)

Pattern 2: Monotonic Increasing Stack (Next Smaller / Width Calculation)

Copy// Pop elements greater than current — compute width on pop
Deque<Integer> stack = new ArrayDeque<>();   // stores indices
for (int i = 0; i <= n; i++) {
    int h = (i == n) ? 0 : nums[i];         // sentinel forces remaining pops
    while (!stack.isEmpty() && nums[stack.peek()] > h) {
        int height = nums[stack.pop()];
        int width  = stack.isEmpty() ? i : i - stack.peek() - 1;
        process(height, width);
    }
    stack.push(i);
}

General Templates

Circular Array Trick

Copy// Traverse the array twice using modulo — covers all circular "next greater" cases
for (int i = 0; i < 2 * n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
        result[stack.pop()] = nums[i % n];
    }
    if (i < n) {
        stack.push(i);              // only push indices in first pass
    }
}

Span Accumulation (Stock Span Style)

Copy// Store [value, span] pairs — collapse runs of smaller values into one entry
Deque<int[]> stack = new ArrayDeque<>();    // [value, accumulated span]
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= current) {
    span += stack.pop()[1];                 // absorb the span of popped entries
}
stack.push(new int[]{current, span});

Problem 1: Next Greater Element I ⭐ MUST DO

Given nums1 (a subset of nums2), return for each element of nums1 the next greater element in nums2. Return -1 if none exists.

Example:

CopyInput:  nums1 = [4,1,2],  nums2 = [1,3,4,2]  →  [-1,3,-1]
Input:  nums1 = [2,4],    nums2 = [1,2,3,4]  →  [3,-1]

Key Insight:

• Process nums2 with a monotonic decreasing stack, building a HashMap from value → next greater value. Then answer each query in nums1 in O(1) using the map. The stack ensures each element in nums2 is processed at most twice — O(n) total.

Solution:

Copypublic int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();    // value → next greater
    Deque<Integer> stack = new ArrayDeque<>();

    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            map.put(stack.pop(), num);              // num is the next greater
        }
        stack.push(num);
    }

    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.getOrDefault(nums1[i], -1);
    }
    return result;
}

Complexity:

Problem 2: Next Greater Element II

Given a circular array, return for each element the next greater element. Wrap around if needed.

Example:

CopyInput:  [1, 2, 1]  →  [2,-1,2]
Input:  [1, 2, 3, 4, 3]  →  [2,3,4,-1,4]

Key Insight:

• Simulate circularity by iterating twice (indices 0 to 2n-1) using i % n. Only push indices in the first pass (i < n) — the second pass is purely for popping unresolved elements by exposing them to elements they couldn't see in the first pass.

Solution:

Copypublic int[] nextGreaterElements(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 < 2 * n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
            result[stack.pop()] = nums[i % n];
        }
        if (i < n) {
            stack.push(i);              // only push in first pass
        }
    }
    return result;
}

Complexity:

Problem 3: Daily Temperatures ⭐ MUST DO

Given daily temperatures, return for each day how many days you must wait for a warmer temperature. Return 0 if no warmer day exists.

Example:

CopyInput:  [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Key Insight:

• Classic next-greater-element, but the answer is the distance (index difference) rather than the value. Store indices on the stack so you can compute i - popped_index when you find a warmer day. The stack remains in decreasing temperature order.

Solution:

Copypublic int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();   // stores indices

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int idx = stack.pop();
            result[idx] = i - idx;              // days until warmer
        }
        stack.push(i);
    }
    return result;
}

Complexity:

Problem 4: Online Stock Span

Design a class that collects daily stock prices and returns the span — the number of consecutive days (including today) where the price was ≤ today's price.

Example:

CopyInput:  prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]

Key Insight:

• Instead of storing individual prices, store [price, span] pairs. When today's price exceeds a previous price, absorb that entry's accumulated span into today's span, then discard it. This collapses runs of lower prices into a single entry, keeping the stack small.

Solution:

Copyclass StockSpanner {
    private Deque<int[]> stack;     // [price, accumulated span]

    public StockSpanner() {
        stack = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];             // absorb span of lower days
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

Complexity:

Problem 5: Largest Rectangle in Histogram ⭐ MUST DO

Given an array of bar heights, find the area of the largest rectangle that can be formed within the histogram.

Example:

CopyInput:  [2, 1, 5, 6, 2, 3]  →  10   (bars 5 and 6, width 2)
Input:  [2, 4]               →  4

Key Insight:

• Maintain a monotonic increasing stack of indices. When a shorter bar is encountered, bars on the stack taller than it can no longer extend rightward — pop and compute their areas now. Width = distance from current index to the new stack top (the previous shorter bar) minus 1. Appending a sentinel 0 forces all remaining bars to be popped at the end.

Solution:

Copypublic int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;

    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];  // sentinel forces final pops
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int width  = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Complexity:

Problem 6: Trapping Rain Water (Stack Approach)

Calculate how much water can be trapped after raining, given an elevation map.

See also: 01_two_pointer.md Problem 13 for the O(1) space two-pointer approach.

Example:

CopyInput:  [0,1,0,2,1,0,1,3,2,1,2,1]  →  6
Input:  [4,2,0,3,2,5]               →  9

Key Insight:

• The stack tracks a decreasing sequence of bars (potential left walls). When a taller bar arrives, it forms a right wall — pop the shorter bar between them (the bottom of the trapped layer), compute the water in that horizontal slice: width × (min(left_wall, right_wall) - bottom_height). Repeat until the stack is not taller than the new bar.

Solution:

Copypublic int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) {
                break;
            }
            int distance     = i - stack.peek() - 1;
            int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[bottom];
            water += distance * boundedHeight;
        }
        stack.push(i);
    }
    return water;
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Monotonic Decreasing Stack (Next Greater)

• "Next greater element" — pop when nums[top] < current
• Store indices when you need the distance, not just the value
• For circular arrays: two passes using i % n; push only in first pass (i < n)
• For span problems: store [value, span] pairs and absorb spans on pop

Monotonic Increasing Stack (Next Smaller / Width)

• "Next smaller element", largest rectangle, or trapped water problems
• Pop when nums[top] > current; compute area/width at pop time
• Width formula after pop: stack.isEmpty() ? i : i - stack.peek() - 1
• Append a sentinel (0) at the end to force all remaining bars to pop and compute

Common Mistakes to Avoid

General Mistakes

1. Storing values instead of indices — most problems require the index to compute distance or width; store stack.push(i) not stack.push(nums[i])
2. Using Stack<> instead of Deque<> — use Deque<Integer> stack = new ArrayDeque<>() with push/pop/peek; the legacy Stack<> class has synchronized overhead

Next Greater Mistakes

3. Wrong pop condition — for next greater, pop when nums[top] < current (strict less than); using <= incorrectly handles equal-valued elements
4. Forgetting the circular second pass — for circular arrays, push indices only when i < n; failing to guard this pushes duplicate indices and corrupts results

Width / Area Mistakes

5. Width formula off by one — after popping, width is i - stack.peek() - 1, not i - stack.peek(); the extra -1 excludes the new stack top (which is the left boundary bar, not part of the width)
6. Forgetting the sentinel — for Largest Rectangle, the loop must go to i = heights.length with h = 0; without it, bars left on the stack at the end are never processed