Monotonic Stack — Next Greater / Smaller Element

Before we start

The monotonic stack is one of those ideas that sounds complicated but rests on a single insight you can state in one sentence. Once you see it, you will recognize it everywhere — in histogram problems, stock prices, and temperature forecasts. By the end you will be able to:

• Explain why the brute-force O(n²) approach is wasteful and what the stack eliminates.
• Write the next-greater-element template from memory.
• Adapt it to next-smaller, previous-greater, and previous-smaller by changing two characters.

Picture this first (no code yet)

The actual problem

Next Greater Element I (LC #496) / Daily Temperatures (LC #739):

Given an array temps = [73, 74, 75, 71, 69, 72, 76, 73], for each day find the number of days you have to wait until a warmer temperature. Return [1, 1, 4, 2, 1, 1, 0, 0].

In general: for each index i, find the index j > i such that arr[j] > arr[i] and j is as small as possible.

First, the slow way (so you feel the pain)

# O(n²) brute force
n = len(temps)
result = [0] * n
for i in range(n):
    for j in range(i + 1, n):
        if temps[j] > temps[i]:
            result[i] = j - i
            break

For n = 100,000 temperatures, this is 10¹⁰ comparisons in the worst case (a decreasing array). At 10⁸ operations per second, that is 100 seconds. The monotonic stack finishes in under a millisecond.

The turning point

The one idea to remember

The template (next greater element)

def dailyTemperatures(temps):
    n      = len(temps)
    result = [0] * n
    stack  = []          # stores indices; values are in decreasing order

    for i, temp in enumerate(temps):
        # while this temp is greater than the temp at the stack's top index
        while stack and temp > temps[stack[-1]]:
            idx         = stack.pop()
            result[idx] = i - idx   # days to wait = current index − popped index

        stack.append(i)  # i hasn't found its answer yet; push it

    # anything left in stack has no warmer day → result stays 0
    return result

Line-by-line narration:

1. result = [0] * n — default is 0 (no warmer day found), which is the correct answer for elements with no greater successor.
2. stack = [] — stores indices (not values). Storing indices lets us compute i - idx for the "days to wait" answer.
3. for i, temp in enumerate(temps): — process left to right.
4. while stack and temp > temps[stack[-1]]: — this element answers all pending smaller elements. "Decreasing stack" means values at the bottom > values at the top; the top is the smallest pending value. If the current temp beats the top, it beats several tops in a row.
5. result[idx] = i - idx — record the gap.
6. stack.append(i) — push current index: it has not yet found its answer.
7. Remaining stack items: no future element was greater — leave result at 0.

Watch it happen, frame by frame

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

i=0, temp=73: stack=[] → push 0.           stack=[0]         result=[0,0,0,0,0,0,0,0]
i=1, temp=74: 74>temps[0]=73 → pop 0, result[0]=1-0=1. Push 1.  stack=[1]
i=2, temp=75: 75>temps[1]=74 → pop 1, result[1]=2-1=1. Push 2.  stack=[2]
i=3, temp=71: 71<75 → push 3.             stack=[2,3]
i=4, temp=69: 69<71 → push 4.             stack=[2,3,4]
i=5, temp=72: 72>temps[4]=69 → pop 4, result[4]=5-4=1.
              72>temps[3]=71 → pop 3, result[3]=5-3=2.
              72<temps[2]=75 → stop. Push 5.  stack=[2,5]
i=6, temp=76: 76>temps[5]=72 → pop 5, result[5]=6-5=1.
              76>temps[2]=75 → pop 2, result[2]=6-2=4.
              stack empty → Push 6.        stack=[6]
i=7, temp=73: 73<76 → push 7.             stack=[6,7]

Loop ends. stack=[6,7] → result[6]=result[7]=0 (no warmer day).

Final: [1, 1, 4, 2, 1, 1, 0, 0]  ✅

Each index was pushed once and popped once — total 2n operations = O(n).

The four variants (one template, two changes)

The monotonic stack template handles four directional questions. Change > to < (or iterate right to left) to cover all cases:

Next Smaller (left → right, increasing stack):

def nextSmaller(arr):
    n, result, stack = len(arr), [-1] * n, []
    for i, val in enumerate(arr):
        while stack and val < arr[stack[-1]]:
            result[stack.pop()] = val   # or i, depending on what "answer" means
        stack.append(i)
    return result

Previous Smaller (right → left, increasing stack):

def prevSmaller(arr):
    n, result, stack = len(arr), [-1] * n, []
    for i in range(n - 1, -1, -1):
        while stack and arr[i] < arr[stack[-1]]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

Next Greater Element I (LC #496) — two arrays

When nums2 is the "universe" and nums1 ⊆ nums2, first compute NGE for all of nums2 using the monotonic stack, store in a hashmap {val → nge}, then look up each element of nums1:

def nextGreaterElement(nums1, nums2):
    nge = {}
    stack = []
    for val in nums2:
        while stack and val > stack[-1]:
            nge[stack.pop()] = val
        stack.append(val)
    for v in stack:
        nge[v] = -1   # no greater element
    return [nge[v] for v in nums1]

Here the stack stores values (not indices) because we don't need index gaps — we need the next greater value itself.

Where to spot this pattern

Trigger words:

• "next greater/smaller element"
• "first warmer day / first day with lower stock"
• "visible buildings / people in queue"
• "span" (stock span problem)
• anything asking for the nearest element to the left/right satisfying a comparison

5 classic problems:

1. Daily Temperatures (LC #739): next greater, return day gap.
2. Next Greater Element I/II (LC #496/503): NGE in another array; NGE in circular array.
3. Online Stock Span (LC #901): consecutive days with price ≤ today — previous-greater variant.
4. Sum of Subarray Minimums (LC #907): use prev/next smaller to count subarrays where each element is the minimum.
5. Largest Rectangle in Histogram (LC #84): uses previous-smaller + next-smaller simultaneously (covered in 5.04).

Common traps

result = [0] * n   # or [-1] * n
stack  = []        # stores indices; decreasing values
for i, val in enumerate(arr):
    while stack and val > arr[stack[-1]]:
        result[stack.pop()] = i   # or val, or i - popped, per problem
    stack.append(i)
# remaining stack → no answer (default stays)

Check yourself

for i in range(2 * n):
    while stack and nums[i % n] > nums[stack[-1]]:
        result[stack.pop()] = nums[i % n]
    if i < n:
        stack.append(i)

Practice problems

Next up: Stack for Parentheses Matching — push opening brackets, pop on closing; a clean O(n) validity check with extensions for minimum removals and score computation.