Monotonic Stack Interview Pattern: Trigger, Template, and Traps

Given an array of daily temperatures, return how many days you would wait for a warmer one. The nested loop is O(n²), and the interviewer is waiting for the other answer. A monotonic stack gets it to O(n): sweep left to right holding a stack of indices that are still waiting for an answer, and let each arriving element resolve every waiting index it beats. Each index is pushed once and popped at most once, so the sweep is linear.

The recognition trigger is narrow, and both halves of it matter: for each element, find the nearest element to its left or right that is bigger or smaller. Drop "nearest" and you want a suffix-max scan. Drop "bigger" and you are in some other pattern entirely.

Key Takeaways

• Reach for the stack only when the statement says nearest and says bigger or smaller. Losing either word changes the tool.
• Never memorize "increasing or decreasing." Decide when an arriving element resolves the stack top; the monotonicity is whatever survives that rule.
• Store indices, not values. Converting a value stack to an index stack halfway through an interview is a nuisance; nums[stack[-1]] costs nothing.
• Every pop hands you both boundaries: the arriving element on the right, the new stack top on the left. Largest-rectangle-in-histogram lives or dies on the second one.
• The O(n) claim needs the amortized argument said out loud. Each index is pushed once and popped at most once, so total pops are bounded by n.

The trigger is "nearest bigger," and nothing looser

Asked at Pinduoduo — Find next greater element for subset Two integer arrays arrive: nums, whose values are all distinct, and query, every value of which appears somewhere in nums. For each queried value, locate it inside nums and report the first strictly larger value standing to its right. Report -1 when nothing to its right is larger. Output one answer per query, in query order.

Here is the brute force, so we are clear about what is being replaced:

def next_greater_bruteforce(nums):
    n = len(nums)
    res = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                res[i] = nums[j]
                break
    return res

O(n²) time, O(1) extra space. On a strictly decreasing array the inner loop never breaks early and you pay the full n²/2 comparisons.

The fix rests on one sentence: the stack holds exactly the elements that have not yet found their answer, and it is sorted. The second half is not a design decision you make. If a sits below b on the stack and b already beat a, then a was popped the moment b arrived. So anything still on the stack is unbeaten by everything above it, which forces the order.

The positional template:

def next_greater(nums):
    n = len(nums)
    res = [-1] * n
    stack = []                        # indices; values non-increasing bottom -> top
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x      # x is the next strictly greater for that index
        stack.append(i)
    return res                        # leftovers keep -1

O(n) time, O(n) space. On [1, 3, 4, 2] this returns [3, 4, -1, -1].

The Pinduoduo variant asks for answers keyed to arbitrary values rather than to positions. Because nums is guaranteed distinct, you can key the map by value and drop the index bookkeeping:

def next_greater_for_query(query, nums):
    nxt = {}
    stack = []                        # values, non-increasing bottom -> top
    for x in nums:
        while stack and stack[-1] < x:
            nxt[stack.pop()] = x
        stack.append(x)
    return [nxt.get(x, -1) for x in query]

With n = len(nums) and m = len(query): O(n + m) time, O(n) space. On the statement's own example (query = [4, 1, 2], nums = [1, 3, 4, 2]) it returns [-1, 3, -1]. Say the distinctness dependency out loud, because it is load-bearing. If a follow-up allows duplicates in nums, keying by value collapses two different positions onto one answer, and you have to key by index instead — which means the query has to arrive as indices too.

That while loop nested inside a for loop looks quadratic and isn't. Each index enters the stack exactly once and leaves at most once, so the total number of pops across the whole run is bounded by n no matter how the array is arranged. That amortization argument is the O(n) claim. "It's O(n) because we use a stack" is not an argument.

Store indices unless you are certain no distance or width will ever be asked for. Daily temperatures is the same scan with the recorded answer changed from a value to a gap:

def daily_temperatures(temps):
    n = len(temps)
    res = [0] * n
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

Days with nothing warmer ahead keep their initialized 0. That is the leftover-on-the-stack case, handled by the initializer instead of by a cleanup loop.

Two things to know before you open the Pinduoduo post: the body is a Chinese 1point3acres trip report covering a full interview loop rather than a standalone question writeup, and the written solution is premium-locked. The console is the part to use. Type the template from memory and run it.

Pick the pop condition and the stack order falls out

People memorize "next greater means decreasing stack," then flip it under pressure. There is only one decision worth making, and that isn't it:

When does an arriving element resolve the element on top of the stack?

Answer that from the problem statement and the monotonicity is a consequence you never think about again. For next-greater, the arriving element resolves the top when arriving > top, so you pop while top < arriving. What survives is everything >= arriving, so the stack reads non-increasing from bottom to top. You did not choose "decreasing." You chose a pop condition and got "decreasing" for free.

The strict versus non-strict asymmetry in the last two rows is where the bugs live. For previous strictly greater, you have to pop equal values as well: leave them and an earlier element carrying the same value survives on the stack, then gets handed back as the current element's previous strictly greater, which it is not. For next strictly greater, do the opposite and leave equals alone, or an equal element gets reported as a strictly greater one. Naming that choice before you write the comparison is cheap and reads as senior.

One pop hands you both boundaries

A pop records two facts. The second is where the harder problems come from.

• The arriving element x is the popped element's next greater to the right.
• The new stack top, after the pop, is the popped element's previous greater-or-equal to the left — strictly greater only when your pop condition also pops equal values.

One pass, both sides. In the next_greater template above the pop condition is strict, so nothing equal to nums[j] was ever popped on j's behalf, and the element sitting below j satisfies nums[below] >= nums[j]. Greater-or-equal, not greater. The histogram code below pops on >=, which is exactly why its left boundary is strictly smaller and its widths come out right.

def largest_rectangle(heights):
    stack = []          # indices, heights increasing bottom -> top
    best = 0
    for i, h in enumerate(heights + [0]):     # sentinel drains the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

O(n) time, O(n) space. Trace [2,1,5,6,2,3]: when 2 arrives at index 4 it pops 6 for area 6, then pops 5 with left boundary index 2 and right boundary index 4, giving 5 * 2 = 10. That is the answer.

The appended 0 sentinel guarantees every bar is eventually popped, so there is no second drain loop with subtly different logic. Equal heights survive this fine: an earlier duplicate computes a too-narrow rectangle, but the last surviving duplicate in a run computes the full width, so the maximum is still found. [2,2] returns 4.

Trapping rain water runs the same machinery with different accounting. Each pop is a puddle floor, walled on the left by the new stack top and on the right by the arriving bar.

def trap(height):
    stack = []          # indices, heights non-increasing
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = height[stack.pop()]
            if not stack:
                break                     # no left wall, water escapes
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], h) - bottom
            water += width * bounded
        stack.append(i)
    return water

O(n) time, O(n) space. On [0,1,0,2,1,0,1,3,2,1,2,1] it returns 6.

If you write this version, volunteer the trade-off before the interviewer asks for it. The two-pointer solution to trapping rain water is also O(n) time but O(1) space, so the stack is not the optimal answer here. It is the answer that generalizes. Being explicit about the space cost beats presenting a second-best solution as a best one.

"Monotonic" in a problem statement usually means something else

Asked at Meta — Optimize ribbon piece length by binary search You are handed an array of ribbon lengths and a target count k. Every ribbon may be cut freely, provided every resulting piece has the same positive integer length L. Find the largest L that still yields at least k pieces overall, and return 0 when no length works. Individual lengths reach 1e9 and k reaches 1e12.

The monotone object here is a predicate, not a data structure. can(L) = sum(x // L for x in lengths) >= k is true for every L at or below the answer and false above it, and that step function is the entire licence to bisect.

def max_piece_length(lengths, k):
    lo, hi, best = 1, max(lengths), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if sum(x // mid for x in lengths) >= k:
            best, lo = mid, mid + 1
        else:
            hi = mid - 1
    return best

O(n log max(lengths)) time, O(1) space. Worth flagging in the interview: with these constraints the piece count reaches 2×10¹⁴ at L = 1, which overflows a 32-bit integer and sits comfortably inside a 64-bit one.

The bank has two more questions that use the word the same way. Implement monotonic-array linear interpolation at Tradedesk hands you a strictly increasing x-array, and the monotonicity is what makes the bracketing binary search legal. Find earliest supporting dependency version at OpenAI is the inverse case: support is explicitly not monotonic across versions, which is precisely why a plain binary search is wrong there and why the interesting part is staying sub-linear in API calls anyway.

No "nearest" in the statement, no stack

Asked at Google — Compute precision–recall curve on imbalanced data A CSV of predicted probabilities and binary labels arrives with a positive rate around 5%. Sweep every distinct probability as a threshold, emit precision, recall and F1 at each one, and deal with ties and empty denominators. Where the task calls for it, force the precision curve to be non-increasing before integrating it into AUPRC, then argue how you would pick an operating threshold under asymmetric costs.

That forcing step is the one that looks like a monotonic-stack job. It isn't. Interpolated precision at a given recall is the best precision achieved at any recall at least that high, which is "best anywhere to the right" with no nearness requirement anywhere in it. A backward running maximum does it:

def monotone_precision(precision):
    """precision[] ordered by increasing recall; returns the non-increasing envelope."""
    env = list(precision)
    for i in range(len(env) - 2, -1, -1):
        env[i] = max(env[i], env[i + 1])
    return env

O(n) time, O(1) extra space if you overwrite in place. [0.9, 0.6, 0.7, 0.4] becomes [0.9, 0.7, 0.7, 0.4]. A stack would produce the same numbers with more code and the same asymptotics. The distinction is worth internalizing because it runs the other way too: on a problem that genuinely needs the nearest larger neighbour, a suffix max hands you the wrong element, not a slower answer.

The sliding-window row is the one that bites. A monotonic deque really is the same idea, but the eviction direction differs and the template does not transfer.

Where the trigger misfires

Asked at Akuna Capital — Compute max profit across dated stock quotes An unsorted pile of (date, symbol, price) records covers several stocks at once, and the same date shows up under different symbols. You may hold at most one share across all symbols, transactions are unlimited, and every buy has to land strictly later than the previous sell. Return the maximum achievable profit together with the actual sequence of trades, and state how you handle repeated or missing (date, symbol) pairs.

Every surface feature points at a monotonic stack. Prices, a left-to-right sweep, comparisons against earlier elements. Nothing in the statement asks for a nearest larger or smaller neighbour, so the trigger should stay quiet.

Start with what the input forbids. The records are unsorted, so you sort or bucket by date before anything else, and O(n log n) is the floor. What remains is a state-machine DP over the distinct dates, with one wrinkle the single-stock version does not have: you sell the share you actually bought, so the holding state has to remember which symbol it holds. A single "best price today" per date is not enough.

free = 0                              # best profit while holding nothing
hold = {}                             # symbol -> best profit while holding that symbol
for d in sorted_dates:
    opening_free = free
    for sym, price in quotes_on[d]:   # sells settle against yesterday's hold
        if sym in hold:
            free = max(free, hold[sym] + price)
    for sym, price in quotes_on[d]:   # buys settle against yesterday's free
        prev = hold.get(sym)
        cand = opening_free - price
        hold[sym] = cand if prev is None else max(prev, cand)

Reading opening_free in the second loop is what enforces "strictly later than the previous sell": a sale booked today cannot fund a purchase today. Because every hold[sym] descends from the single scalar free, you can never be holding two symbols at once. After the sweep, free is the maximum profit.

Returning the trade list on top of the number means carrying parent pointers through both loops, which costs O(number of records) extra space — so an O(1)-space claim is off the table here as well. Total: O(n log n) time dominated by the sort, O(n) space. A candidate who pattern-matches "stock prices" to the one-pass running-minimum solution has answered the single-transaction problem instead, which is a different and much easier question.

Sorting is the wrong turn that costs the most on genuine stack problems, and it is easy to make without noticing. Sorting destroys the positional relationship that "nearest" is defined against, and the test cases are usually where you find out.

Practice these on PracHub

Run the template cold

• Find next greater element for subset — Pinduoduo. The scan in its purest form. Distinct values let you key the answer map by value; check the -1 path for elements near the end of nums.

Calibrate the trigger — none of these are stack problems

• Compute max profit across dated stock quotes — Akuna Capital. Tests whether you can tell a per-element neighbour query from a state-machine DP, and whether you notice the unsorted input before quoting a complexity.
• Find earliest common meeting slot — Uber. Merge N sorted busy-interval lists and intersect with working hours. The answer comes from a sweep over interval boundaries, not from any element's nearest larger neighbour.
• Compute precision–recall curve on imbalanced data — Google. The monotone envelope step is a backward running max. Reaching for a stack means you matched on the word "monotonic."

Where "monotonic" means a predicate, not a stack

• Optimize ribbon piece length by binary search — Meta. Binary search on the answer with a monotone feasibility check, plus 64-bit counting.
• Find horizontal cut balancing square areas — Google. The same skeleton on a continuous parameter: area-above is monotone in y, so you bisect and then have to defend a stopping criterion under float coordinates.
• Implement monotonic-array linear interpolation — Tradedesk. A strictly increasing x-array, a bracketing binary search, and the edge cases outside the domain.
• Find earliest supporting dependency version — OpenAI. Monotonicity is explicitly broken and the API is rate-limited, so you have to stay sub-linear in calls without it.

FAQ

What is a monotonic stack?

A stack whose contents stay sorted, either non-increasing or non-decreasing from bottom to top, maintained by popping elements that violate the order before each push. Its contents are exactly the elements still waiting for an answer, which is why the sort order holds automatically rather than being enforced. It turns "for each element, find the nearest bigger or smaller one" from O(n²) into O(n).

Should a monotonic stack be increasing or decreasing?

Do not decide that directly. Decide when an arriving element resolves the top of the stack, pop while that condition holds, and the monotonicity follows. For next-greater you pop while top < arriving, which leaves a non-increasing stack; for next-smaller you pop while top > arriving, which leaves a non-decreasing one. Deriving it takes a few seconds and never flips under pressure.

Why is a monotonic stack O(n) when there is a while loop inside a for loop?

Because the inner loop's work is bounded globally rather than per iteration. Each index is pushed exactly once and popped at most once across the entire run, so total pops are at most n regardless of the input arrangement. A single outer iteration can pop many elements, but it can only pop elements that some earlier iteration pushed.

When is a monotonic stack the wrong tool?

When the statement lacks "nearest" or lacks "bigger/smaller." Max over a sliding window needs a monotonic deque, because elements expire by index from the front and a stack cannot evict from its bottom. Best value anywhere on one side is a suffix or prefix maximum. Ranked queries need a sorted container or BIT, and anything with insertions or deletions needs a balanced BST or segment tree, since the stack is one-pass and append-only.

Does a monotonic stack handle duplicate values?

Yes, provided the comparison is chosen deliberately. For next strictly greater, pop on < so equal values stay stacked and an equal element is never reported as a greater one. For previous strictly greater, pop on <=: if you leave equals on the stack, an earlier element with the same value gets handed back as the current element's previous strictly greater, which is wrong. In largest-rectangle-in-histogram, popping equal heights is safe because the last duplicate in a run recomputes the full width and dominates the earlier partial ones.

What happens to the elements still on the stack when the loop ends?

They never found an answer, so they take whatever sentinel the problem defines: -1 for next-greater, 0 for daily temperatures. Initialize the result array with that value and no cleanup loop is needed at all. The alternative is appending a sentinel to the input, such as + [0] for histograms, so the main loop drains the stack for you.