Monotonic Stacks Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When you see a problem that asks for the first element larger (or smaller) than the current one on either side, you are probably looking at a monotonic‑stack pattern. The idea is simple: maintain a stack whose values are always increasing (or decreasing). As you scan the array, you can answer each query in constant amortized time, turning what would be an O(n²) brute force into O(n).

Why a Stack?

A stack gives you last‑in‑first‑out access, which matches the way you need to backtrack when a new element invalidates older candidates. By keeping the stack monotonic, you guarantee that any element you pop can never become the answer for any future index – it is already dominated by the current element. This property lets you discard work permanently, which is why the overall cost stays linear.

Signals That a Problem Wants a Monotonic Stack

If any of these phrases appear, pause and consider a monotonic stack.

Worked Example: Next Greater Element

Problem: Given an array nums, return an array ans where ans[i] is the first element to the right of i that is larger than nums[i]. If none exists, use -1.

Intuition: Scan from right to left. While the stack’s top is less‑or‑equal to the current value, pop it – it can’t be the next greater for any earlier element. The remaining top, if any, is the answer for the current index.

Python code:

from typing import List

def next_greater(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [-1] * n
    stack: List[int] = []          # will store indices
    for i in range(n - 1, -1, -1):
        # discard elements that are not greater
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()
        # top now holds the next greater index, if any
        if stack:
            ans[i] = nums[stack[-1]]
        # push current index for future queries
        stack.append(i)
    return ans

Complexity: Each index is pushed once and popped at most once, so the time is O(n) and extra space is O(n) for the stack and answer array.

Common Pitfalls

• Wrong direction – forgetting whether you need to scan left‑to‑right or right‑to‑left. The direction depends on whether you want the next or previous element.
• Storing values vs. indices – storing values loses the ability to compute distances; keep indices unless you only need the value.
• Equality handling – decide early whether “greater” means > or >=. A mismatch leads to off‑by‑one errors.
• Not resetting the stack – when solving multiple independent test cases in one run, remember to clear the stack.
• Mixing monotonicities – a decreasing stack is needed for “next smaller element” problems; using an increasing stack will give wrong answers.

Five Practice Problems

Below are five problems that each highlight a different twist on the monotonic‑stack idea. The descriptions are original; they do not copy any existing statement.

1. Daily Temperatures (LeetCode‑style)

Task: For each day, compute how many days you must wait until a warmer temperature appears. Return 0 if no warmer day exists. Hint: Scan from right to left with a decreasing stack of temperatures. When you encounter a warmer day, pop colder days until the top is warmer.

2. Largest Rectangle in a Histogram

Task: Given an array of bar heights, find the maximal area of a rectangle formed by consecutive bars. Hint: Use a monotonic increasing stack to locate the left and right boundaries where each bar becomes the smallest. Compute area as height * (right - left - 1).

3. Sum of Subarray Minimums

Task: Compute the sum of the minimum element of every subarray, modulo a large prime. Hint: A monotonic increasing stack helps you count how many subarrays have a particular element as the minimum. Track the distance to the previous smaller and next smaller element.

4. Minimum Number of Removals to Make a Sequence Increasing

Task: Given a sequence, find the smallest number of elements to delete so that the remaining sequence is strictly increasing. Hint: Transform the problem into finding the length of the longest increasing subsequence (LIS). A variant of the monotonic stack—maintaining a list of smallest possible tail values—runs in O(n log n).

5. Sliding Window Maximum

Task: For a fixed window size k, output the maximum of each sliding window across the array. Hint: Maintain a decreasing deque (double‑ended queue) that stores indices of candidates for the maximum. Remove indices that fall out of the window and those that are smaller than the incoming element.

When to Reach for a Monotonic Stack

• The problem asks for nearest greater/smaller values.
• You need to compute a span or range where a condition holds.
• The answer can be expressed as a function of distances to the previous/next element that breaks a monotonic property.
• You can formulate the solution as a single pass with a stack that only grows and shrinks monotonically.

How to Practice This

1. Write the core loop first – focus on the push/pop logic without worrying about edge cases. Verify with a tiny hand‑crafted array.
2. Swap direction – take a problem that uses “next greater” and rewrite it for “previous greater”. This reinforces the scan direction rule.
3. Explain aloud – use Call Assistant to rehearse your solution narrative. Speaking the algorithm helps you spot missing steps and keeps the interview flow tight.

FAQ

• Q: How does a monotonic stack differ from a regular stack? A: A regular stack has no ordering constraints; a monotonic stack enforces that its elements are always increasing (or decreasing). This constraint lets you discard elements permanently, guaranteeing linear time.
• Q: Can I use a deque instead of a stack? A: Yes, especially for sliding‑window problems where you need to remove elements from the front as the window moves. The deque still respects a monotonic order.
• Q: What if the problem asks for the k‑th greater element instead of the first? A: The classic monotonic‑stack pattern solves the first occurrence. For the k‑th, you often need additional data structures (e.g., a balanced BST) or a modified stack that stores counts.
• Q: Is the monotonic‑stack pattern applicable to strings? A: It can be, when the condition is based on lexicographic order or numeric values derived from characters. The same push/pop principle applies.