Monotonic Stack

Use when: Next greater/smaller element, span problems, largest rectangle.

Complexity: O(N) - each element pushed and popped at most once

Next Greater Element

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices, decreasing values
 
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
 
    return result

Next Smaller Element

def next_smaller(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices, increasing values
 
    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
 
    return result

Previous Greater Element

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

Largest Rectangle in Histogram

def largest_rectangle(heights):
    stack = []  # monotonic increasing stack of indices
    max_area = 0
    heights.append(0)  # sentinel
 
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            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

Signals in a Problem

• “Next greater/smaller element”
• “Daily temperatures”, “stock span”
• “Largest rectangle” / “trap rain water”
• Need to find nearest element satisfying a condition