Monotonic Stack Questions 2026: 16+ Problems [Solved]

Last Updated: June 2026

Why Monotonic Stack is a High-Value Pattern

Candidates report monotonic stack as a pattern interviewers specifically probe for, since it distinguishes candidates who know O(n) solutions from those who write O(n^2). Based on public preparation resources and candidate-reported interview threads, questions like "Largest Rectangle in Histogram" and "Next Greater Element" are staples in Amazon, Google, and Goldman Sachs rounds.

What Makes a Stack "Monotonic"

A regular stack follows last-in-first-out order with no ordering constraint on values. A monotonic stack adds the constraint that elements are always in sorted order from bottom to top. The trick is the maintenance rule: before pushing a new element, pop all elements that violate the ordering property. This means the stack never contains an element that would make it non-monotone, and every pop produces a useful result (the next greater or smaller element for the popped index).

The two variants differ only in which direction breaks the ordering. Which one you need is determined by what the problem is asking: next greater (decreasing stack) versus next smaller (increasing stack).

Monotonic Increasing Stack:
  Elements from bottom to top are in increasing order.
  When pushing x: pop all elements >= x first.
  Use for: next smaller element, largest rectangle.

Monotonic Decreasing Stack:
  Elements from bottom to top are in decreasing order.
  When pushing x: pop all elements <= x first.
  Use for: next greater element, stock span, temperature.

Templates

Monotonic Decreasing (Next Greater Element)

def next_greater_element_template(arr):
    """
    For each element, find the next element to its right that is greater.
    Time: O(n)  Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices, decreasing values

    for i in range(n):
        # Pop while current is greater than stack top
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

Monotonic Increasing (Next Smaller Element)

def next_smaller_element_template(arr):
    """
    For each element, find the next element to its right that is smaller.
    Time: O(n)  Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices, increasing values

    for i in range(n):
        while stack and arr[i] < arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

Practice Questions with Solutions

Problem 1: Next Greater Element I (EASY)

Asked at: Amazon, Google, Microsoft

def next_greater_element(nums1, nums2):
    """
    For each element in nums1, find its next greater element in nums2.
    Precompute nge map for nums2.
    Time: O(n + m)  Space: O(n)
    """
    nge = {}
    stack = []

    for num in nums2:
        while stack and num > stack[-1]:
            nge[stack.pop()] = num
        stack.append(num)

    return [nge.get(num, -1) for num in nums1]

# Example
print(next_greater_element([4, 1, 2], [1, 3, 4, 2]))   # [-1, 3, -1]
print(next_greater_element([2, 4], [1, 2, 3, 4]))       # [3, -1]

Complexity: Time O(n + m), Space O(n)

Problem 2: Next Greater Element II (Circular Array) (MEDIUM)

Asked at: Amazon, Google

def next_greater_elements_circular(nums):
    """
    Circular: loop twice (process indices 0..2n-1 mod n).
    Time: O(n)  Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []

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

    return result

# Example
print(next_greater_elements_circular([1, 2, 1]))  # [2, -1, 2]

Complexity: Time O(n), Space O(n)

Problem 3: Daily Temperatures (MEDIUM)

Asked at: Amazon, Google, Facebook - classic monotonic stack

def daily_temperatures(temperatures):
    """
    For each day, how many days until a warmer temperature?
    Monotonic decreasing stack of indices.
    Time: O(n)  Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

# Example
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Complexity: Time O(n), Space O(n)

Problem 4: Stock Span Problem (MEDIUM)

Asked at: Amazon, Goldman Sachs, Morgan Stanley

def stock_span(prices):
    """
    Span of price[i] = consecutive days (ending today) where price <= price[i].
    Monotonic decreasing stack.
    Time: O(n)  Space: O(n)
    """
    n = len(prices)
    span = [1] * n
    stack = []  # stores indices

    for i in range(n):
        while stack and prices[i] >= prices[stack[-1]]:
            stack.pop()
        span[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    return span

# Example
print(stock_span([100, 80, 60, 70, 60, 75, 85]))
# [1, 1, 1, 2, 1, 4, 6]

Complexity: Time O(n), Space O(n)

Problem 5: Largest Rectangle in Histogram (HARD)

Asked at: Amazon, Google, Microsoft, Goldman Sachs - classic hard stack problem

def largest_rectangle_area(heights):
    """
    Monotonic increasing stack of indices.
    When popped at index i (due to heights[i] < heights[stack top]):
      width = i - stack[-1] - 1 (or i if stack empty)
      area = heights[popped] * width
    Time: O(n)  Space: O(n)
    """
    n = len(heights)
    stack = []
    max_area = 0

    for i in range(n + 1):
        h = heights[i] if i < n else 0  # sentinel 0 at end

        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

# Example
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 10 (bars 5 and 6)
print(largest_rectangle_area([2, 4]))               # 4

Complexity: Time O(n), Space O(n)

Problem 6: Maximal Rectangle (HARD)

Asked at: Amazon, Google - extends histogram to 2D

def maximal_rectangle(matrix):
    """
    Convert each row to a histogram (cumulative heights).
    Apply largest_rectangle_area to each histogram.
    Time: O(m*n)  Space: O(n)
    """
    if not matrix or not matrix[0]:
        return 0

    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, largest_rectangle_area(heights))

    return max_area

# Example
matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]
print(maximal_rectangle(matrix))  # 6

Complexity: Time O(m*n), Space O(n)

Problem 7: Trapping Rain Water (HARD) - Monotonic Stack Approach

Asked at: Amazon, Google, Microsoft, Goldman Sachs

def trap_stack(height):
    """
    Monotonic decreasing stack.
    When popped, water trapped between left wall, current bar, and right wall.
    Time: O(n)  Space: O(n)
    """
    stack = []
    water = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], height[i]) - height[bottom]
            water += width * bounded_height

        stack.append(i)

    return water

# Example
print(trap_stack([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

Complexity: Time O(n), Space O(n)

Problem 8: Sum of Subarray Minimums (MEDIUM)

Asked at: Amazon, Google, Facebook

def sum_subarray_mins(arr):
    """
    For each element, find how many subarrays have it as minimum.
    = (elements on left until smaller) * (elements on right until smaller or equal).
    Use monotonic stack to find these boundaries.
    Time: O(n)  Space: O(n)
    """
    MOD = 10**9 + 7
    n = len(arr)

    # left[i] = distance to previous smaller element (or left boundary)
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # right[i] = distance to next smaller or equal element (or right boundary)
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    result = sum(arr[i] * left[i] * right[i] for i in range(n))
    return result % MOD

# Example
print(sum_subarray_mins([3, 1, 2, 4]))  # 17
print(sum_subarray_mins([11, 81, 94, 43, 3]))  # 444

Complexity: Time O(n), Space O(n)

Problem 9: Remove K Digits (MEDIUM)

Asked at: Amazon, Google, Bloomberg

def remove_k_digits(num, k):
    """
    Greedily remove digits to get smallest number.
    Maintain monotonic increasing stack; pop when larger digit seen and k > 0.
    Time: O(n)  Space: O(n)
    """
    stack = []

    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # If k still > 0, remove from end
    if k:
        stack = stack[:-k]

    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result or '0'

# Example
print(remove_k_digits("1432219", 3))  # "1219"
print(remove_k_digits("10200", 1))    # "200" -> "200"
print(remove_k_digits("10", 2))       # "0"

Complexity: Time O(n), Space O(n)

Problem 10: 132 Pattern (MEDIUM)

Asked at: Amazon, Google

def find132pattern(nums):
    """
    Find i < j < k such that nums[i] < nums[k] < nums[j].
    Scan right to left. Stack tracks potential "3" values.
    third tracks current best "2" candidate.
    Time: O(n)  Space: O(n)
    """
    stack = []
    third = float('-inf')   # the "2" in 1-3-2 pattern (k value)

    for num in reversed(nums):
        if num < third:
            return True
        while stack and stack[-1] < num:
            third = stack.pop()
        stack.append(num)

    return False

# Example
print(find132pattern([1, 2, 3, 4]))   # False
print(find132pattern([3, 1, 4, 2]))   # True
print(find132pattern([-1, 3, 2, 0]))  # True

Complexity: Time O(n), Space O(n)

Monotonic Stack Pattern Recognition

Complexity Summary

Why Monotonic Stack Achieves O(n)

The key insight is amortized analysis. Each element is pushed onto the stack exactly once and popped at most once. So even though the inner while loop pops multiple elements, the total number of push and pop operations across the entire iteration is bounded by 2n. This gives O(n) total work, not O(n^2) as the nested loop structure might suggest.

This amortized argument is what you must explain when an interviewer asks "but why is this O(n) when there is a while loop inside a for loop?" The answer: each element participates in at most two operations total (one push, one pop).

Comparing Monotonic Stack vs Sliding Window

Both patterns run in O(n), but they solve different sub-problems. Sliding window maintains a contiguous window and is driven by a sum or count condition. Monotonic stack maintains relative ordering of elements and finds the first element that breaks the monotone property. Problems asking "next greater/smaller" or computing spans are almost always monotonic stack, not sliding window.

The maximal rectangle problem is a canonical example where monotonic stack is the only clean O(n) approach. The two-pointer approach people attempt leads to O(n^2) once they try to compute widths correctly.

Monotonic Stack vs Brute Force: The Complexity Argument

When you see a problem asking "for each element, find the next element satisfying condition X", the brute force is a nested loop: O(n^2). The monotonic stack achieves O(n) by ensuring that each element is pushed once and popped once. This amortized argument must be explicitly stated in interviews - just showing O(n) code without explaining why the inner while loop does not create O(n^2) is a weak answer.

The stock span problem illustrates this clearly. For each day, a naive approach rescans backwards until a higher price is found, giving O(n^2). The stack approach processes each price in constant amortized time by remembering the useful historical context.

Monotonic Stack in Practice: Problems That Look Different But Are the Same

Many problems that appear unrelated share the same monotonic stack core. The "sum of subarray minimums" problem looks like a DP problem until you realize it is asking "for each element, how many subarrays have this element as minimum?", which is a span calculation. The "132 pattern" looks like a search problem until you realize the stack maintains candidate "3" values in decreasing order.

Recognizing these disguised forms is what separates a candidate who has memorized solutions from one who understands the pattern. When an interviewer asks "what if the array has negative numbers?", the answer is that monotonic stack still works - the monotone ordering is on values, not on whether values are positive.

How to Debug Monotonic Stack Code

The most reliable debugging technique is to trace through a small example (five to six elements) manually, writing out the stack state after each iteration. Compare the final result array against brute force. Off-by-one errors in width calculation for rectangles and wrong inequality direction (> vs >=) are the two most common failure modes.

Common Mistakes

1. Circular array off-by-one: When processing 2n indices, only push to stack for i < n.
2. Width calculation in rectangle: Width = right_boundary - left_boundary - 1, not right_boundary - left_boundary.
3. Popping condition for duplicates: Use >= (not >) to avoid counting duplicate spans twice.

Related Articles

• Stack Queue Questions Placement
• Arrays Questions Placement
• Sliding Window Pattern Questions 2026
• Top K Elements Pattern 2026
• Must-Do Coding Questions