Monotonic Stack Pattern

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

​

What is Monotonic Stack?

​

Pattern Recognition Cheatsheet

​

Reusable Template Code

# Skeleton 1: NEXT greater (or smaller) -- resolve on POP
def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []                              # store INDICES
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            j = stack.pop()
            result[j] = nums[i]             # popped index found its answer
        stack.append(i)
    return result                           # leftover indices stay -1

# Skeleton 2: PREVIOUS smaller (or greater) -- resolve on PUSH
def previous_smaller(nums):
    n = len(nums)
    result = [-1] * n
    stack = []                              # increasing
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        if stack:
            result[i] = nums[stack[-1]]     # whatever survives is the answer
        stack.append(i)
    return result

# Skeleton 3: Histogram-style "compute on pop" with sentinel
def histogram_area(heights):
    stack = []
    max_area = 0
    heights = heights + [0]                 # sentinel forces final flush
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * width)
        stack.append(i)
    return max_area

​

When to Use

​

Pattern Variations

​

1. Next Greater Element

def next_greater_element(nums):
    """For each element, find the next element to its right that is larger.
    Return -1 if no such element exists.
    
    Walkthrough with [2, 1, 2, 4, 3]:
      i=0: stack=[]       -> push 0.           stack=[0]
      i=1: nums[1]=1 < nums[0]=2 -> push 1.   stack=[0,1]
      i=2: nums[2]=2 > nums[1]=1 -> pop 1, result[1]=2.
           nums[2]=2 == nums[0]=2 (not >), stop. push 2.  stack=[0,2]
      i=3: nums[3]=4 > nums[2]=2 -> pop 2, result[2]=4.
           nums[3]=4 > nums[0]=2 -> pop 0, result[0]=4.
           push 3.  stack=[3]
      i=4: nums[4]=3 < nums[3]=4 -> push 4.   stack=[3,4]
    Remaining in stack have no next greater -> stay -1.
    Result: [4, 2, 4, -1, -1]
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Indices of elements waiting for their next greater
    
    for i in range(n):
        # Pop all elements smaller than the current -- they found their answer
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

​

2. Previous Smaller Element

def previous_smaller(nums):
    """For each element, find the nearest smaller element to its left.
    Return -1 if none exists.
    
    Example: [3, 5, 2, 7, 4]
      i=0: stack empty -> result[0] = -1.  push 0.
      i=1: nums[0]=3 < 5 -> result[1] = 3. push 1.
      i=2: pop 1 (5 >= 2), pop 0 (3 >= 2) -> stack empty, result[2] = -1. push 2.
      i=3: nums[2]=2 < 7 -> result[3] = 2. push 3.
      i=4: pop 3 (7 >= 4), nums[2]=2 < 4 -> result[4] = 2. push 4.
    Result: [-1, 3, -1, 2, 2]
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Monotonic increasing stack of indices
    
    for i in range(n):
        # Pop elements that are NOT smaller than the current element
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        
        # Stack top (if any) is the previous smaller element
        if stack:
            result[i] = nums[stack[-1]]
        
        stack.append(i)
    
    return result

​

3. Largest Rectangle in Histogram

def largest_rectangle_area(heights):
    """Find the area of the largest rectangle in a histogram.
    
    Example: heights = [2, 1, 5, 6, 2, 3]
    The largest rectangle has area 10 (height 5, spanning indices 2-3).
    """
    stack = []   # Stack of (start_index, height) -- monotonic increasing by height
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i  # Track how far back this height can extend
        # Pop bars taller than current -- they can no longer extend right
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))  # Width = i - idx
            start = idx  # Current bar can extend back to where popped bar started
        stack.append((start, h))
    
    # Remaining bars in the stack extend all the way to the right edge
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    
    return max_area

​

4. Daily Temperatures

def daily_temperatures(temperatures):
    """For each day, find how many days until a warmer temperature.
    Return 0 if no warmer day exists.
    
    Example: [73, 74, 75, 71, 69, 72, 76, 73]
    Result:  [ 1,  1,  4,  2,  1,  1,  0,  0]
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Indices of days still waiting for a warmer day
    
    for i in range(n):
        # Current day is warmer than days on the stack -- resolve them
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx  # Distance in days
        stack.append(i)
    
    # Days remaining in the stack never found a warmer day -> result stays 0
    return result

​

5. Trapping Rain Water

def trap(height):
    """Calculate trapped rainwater using a monotonic stack.
    
    Strategy: maintain a decreasing stack. When we find a bar taller than
    the stack top, water is trapped between the current bar and the bar
    under the popped element. We compute water layer by layer.
    
    Example: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] -> 6 units of water
    """
    stack = []   # Indices forming a decreasing sequence of heights
    water = 0
    
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()       # The "valley floor"
            if not stack:
                break                  # No left wall -> water spills out
            
            # Water trapped between left wall (stack top) and right wall (i)
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - height[bottom]
            water += width * bounded_height
        
        stack.append(i)
    
    return water

​

How to Choose Increasing vs Decreasing

​

Worked LeetCode Problems: Brute Force vs Optimized

​

LC 496: Next Greater Element I (Easy)

def next_greater_element(nums1, nums2):
    nge = {}                                  # value -> next greater
    stack = []
    for x in nums2:
        while stack and stack[-1] < x:
            nge[stack.pop()] = x              # popped value's answer is x
        stack.append(x)
    # Anything left has no next greater
    return [nge.get(v, -1) for v in nums1]

​

LC 739: Daily Temperatures (Medium)

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []                                # indices waiting for a warmer day
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j                 # distance, not value
        stack.append(i)
    return result

​

LC 84: Largest Rectangle in Histogram (Hard)

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights = heights + [0]                   # sentinel forces flush at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * width)
        stack.append(i)
    return max_area

​

LC 42: Trapping Rain Water (Hard) — Stack Approach

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

​

Caveats and Traps

​

Curated LeetCode Practice List

​

Easy

​

Medium

​

Hard

​

Classic Problems

​

Practice Problems

​

Interview Questions

​

1. Explain the monotonic stack pattern. Why does it reduce the “next greater element” problem from O(n^2) to O(n)?

• A monotonic stack maintains elements in sorted order (increasing or decreasing). For “next greater element,” we use a decreasing stack (bottom to top). We iterate through the array; for each new element, we pop all stack elements smaller than it — each popped element just found its next greater element (the current element).
• The O(n) proof: every element is pushed exactly once and popped at most once. Across the entire loop, we do at most n pushes and at most n pops, giving 2n total operations — O(n). The while loop inside the for loop is misleading; it looks nested, but the total work across all iterations is bounded by n pops.
• Think of it like a bouncer at a club with a height rule. When a tall person arrives, the bouncer removes everyone shorter in line. Each person enters and leaves the line at most once.
• After processing the entire array, any elements remaining on the stack have no next greater element — their answer is -1 (or whatever the default is).

1. How would you modify this to find the “next greater or equal” element instead of “strictly greater”?
2. If the array is circular (the element after the last wraps to the first), how do you adapt the monotonic stack approach?

​

2. When do you use an increasing vs. decreasing monotonic stack? Give the decision rule.

• The rule is: the stack direction is opposite to what you are searching for. Looking for the “next greater”? You need elements waiting on the stack to be in decreasing order, so that a larger arriving element triggers resolution. Looking for the “next smaller”? You need increasing order, so that a smaller element triggers resolution.
• For “next” problems (looking rightward), the answer is found on pop — the popped element found its answer when a new element violated the stack’s ordering. For “previous” problems (looking leftward), the answer is found on push — whatever remains on the stack top after popping is the nearest element in that direction.
• Concrete mapping: Next Greater = decreasing stack, pop when current is greater than top. Next Smaller = increasing stack, pop when current is less than top. Previous Greater = decreasing stack, answer is stack top before pushing. Previous Smaller = increasing stack, answer is stack top before pushing.
• Memory trick I use: “Next resolves on pop, Previous resolves on push.” This one-liner covers all four variants.

1. For the “Sum of Subarray Minimums” problem, you need both the previous smaller and next smaller element for each position. How do you combine two monotonic stack passes?
2. What happens with duplicate values? Does “strictly less than” vs “less than or equal” in the pop condition change which stack direction you use?

​

3. Walk me through how the “Largest Rectangle in Histogram” problem works with a monotonic stack.

• The core idea: for each bar, find how far it can extend left and right as the shortest bar. The rectangle area for that bar is height * (right_boundary - left_boundary). A monotonic increasing stack (by height) lets us compute both boundaries efficiently.
• We maintain a stack of (start_index, height) pairs in increasing order of height. When we encounter a bar shorter than the stack top, we pop — the popped bar can no longer extend right (the current bar blocks it). Its area is height * (current_index - start_index). Crucially, the current shorter bar can extend back to where the popped bar started, so we track start = popped.start_index.
• After processing all bars, anything left on the stack extends all the way to the right edge of the histogram. For each remaining (start, height), the area is height * (n - start).
• Example: heights [2, 1, 5, 6, 2, 3]. The largest rectangle is height 2, spanning indices 0-5, giving area 26 = 12. Wait — actually it is height 5 spanning indices 2-3, area 10? Let me recheck: height 2 from index 0 to 5 gives 26=12. But the bar at index 1 has height 1, which blocks the height-2 bar. The actual answer is 10 (height 5 across indices 2-3). This kind of careful walkthrough is what interviewers want to see.

1. How do you extend this to “Maximal Rectangle” in a 2D binary matrix?
2. Could you solve this problem with a divide-and-conquer approach? What would the complexity be?

​

4. Solve “Daily Temperatures” — for each day, find how many days until a warmer temperature. How is this different from “Next Greater Element”?

• This is exactly the “Next Greater Element” pattern, but instead of recording the value of the next greater element, we record the distance (index difference). The stack holds indices of days still waiting for a warmer day.
• Iterate through temperatures. For each day i, while the stack is non-empty and temperatures[i] > temperatures[stack.top()], pop the top index idx and set result[idx] = i - idx. Then push i.
• Days remaining on the stack after the loop never find a warmer day, so their result stays 0 (the default).
• The structural difference from the basic “Next Greater Element” is purely in what we record: result[idx] = nums[i] (value) vs. result[idx] = i - idx (distance). The stack logic is identical. Recognizing this mapping is the skill — once you see it, the problem is a 5-minute solve.

1. What if we also need to find how many days until a cooler temperature? How does the stack direction change?
2. Can you solve this problem in O(n) time with O(1) extra space (not counting the output array)? Hint: traverse from right to left.

​

5. Explain how the stack-based approach for “Trapping Rain Water” works. How does it differ from the two-pointer approach?

• The stack approach processes water horizontally, layer by layer. We maintain a decreasing stack of bar indices. When we encounter a bar taller than the stack top, water is trapped between the current bar (right wall) and the bar below the popped element (left wall). The water volume for that layer is width * bounded_height, where width = i - stack.top() - 1 and bounded_height = min(height[i], height[stack.top()]) - height[popped].
• The two-pointer approach processes water vertically, column by column. Two pointers start at both ends, and we track left_max and right_max. At each step, move the pointer with the smaller max inward. The water above the current bar is max_on_its_side - height[current].
• Trade-off: the stack approach uses O(n) space and is harder to implement correctly (the three-element interaction of current, popped, and stack top is error-prone). The two-pointer approach uses O(1) space and is conceptually elegant. Both are O(n) time.
• There is also a third approach: build left_max[] and right_max[] prefix/suffix arrays, then for each bar, water = min(left_max[i], right_max[i]) - height[i]. This is O(n) time and O(n) space — easiest to understand, moderate space.

1. Why does the two-pointer approach move the pointer with the smaller max? What breaks if you move the other one?
2. Can this problem be extended to 3D (trapping water on a 2D elevation map)? What data structure would you use?

​

6. What is the “contribution technique” used in “Sum of Subarray Minimums”? How does a monotonic stack enable it?

• Instead of finding the minimum of every subarray (O(n^2) subarrays), we flip the question: for each element nums[i], in how many subarrays is it the minimum? Its contribution to the total sum is nums[i] * count_of_subarrays_where_it_is_minimum.
• To count those subarrays, we need to find how far left and right nums[i] extends as the minimum. Let left[i] = distance to the previous smaller element, and right[i] = distance to the next smaller (or equal) element. The number of subarrays where nums[i] is the minimum is left[i] * right[i].
• We use two monotonic stack passes: one left-to-right for previous smaller (increasing stack), one right-to-left for next smaller or equal (increasing stack). The “or equal” on one side prevents double-counting when duplicate values exist.
• Total sum = sum of nums[i] * left[i] * right[i] for all i. Time is O(n), space is O(n). This technique generalizes to “Sum of Subarray Maximums,” “Sum of Subarray Ranges,” and similar problems.

1. Why does one boundary use strict less-than and the other uses less-than-or-equal? What happens if you use strict less-than on both?
2. How would you adapt this technique to compute “Sum of Subarray Ranges” (max - min for every subarray)?

​

7. You have a circular array and need to find the next greater element for each position, where the search wraps around. How do you handle this?

• The trick is to iterate through the array twice (indices 0 to 2n-1) and use i % n to get the actual index. This simulates the circular wrap-around. In the first pass, elements find their next greater if it exists to the right. In the second pass, elements that wrap around find their next greater from the beginning of the array.
• We only push indices during the first pass (when i is less than n) to avoid duplicating entries. During the second pass, we only pop and resolve — we do not push new indices because those are duplicates.
• Actually, the cleaner implementation pushes i % n for all i in [0, 2n) and checks stack elements as usual, but only initializes the result array with -1 for size n. Each element can be pushed up to twice and popped up to twice, so total operations are O(n). The result array only stores answers for the original n positions.
• Example: [2, 1, 2, 4, 3] — the element 3 at index 4 has no next greater in the linear case (-1), but in the circular case, wrapping around, its next greater is 4 at index 3.

1. Does the circular approach change the time complexity? What about space?
2. Can you think of a problem where the circular monotonic stack variant is useful in a real system (not just a LeetCode exercise)?

​

Interview Deep-Dive

​

Interview Q&A Rapid-Fire (Rich Format)

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []                            # indices of waiting days, decreasing temps
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j             # day-distance, not temperature value
        stack.append(i)
    return result

# Approach 1: Two pointers -- O(n) time, O(1) space
def trap_two_pointer(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

# Approach 2: Monotonic decreasing stack -- O(n) time, O(n) space, layer-by-layer
def trap_stack(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()
            if not stack: break           # no left wall -> water escapes
            width = i - stack[-1] - 1
            bounded = min(h, height[stack[-1]]) - height[bottom]
            water += width * bounded
        stack.append(i)
    return water

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights = heights + [0]               # sentinel forces flush
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * width)
        stack.append(i)
    return max_area

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    # left[i] = distance to previous STRICTLY smaller (or i+1 if none)
    # right[i] = distance to next SMALLER-OR-EQUAL (or n-i if none)
    left = [0] * n
    right = [0] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:    # >= to be strict on left
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:     # > to be non-strict on right
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)
    return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD