Monotonic Stack

Use Cases

Use Case	Description	Example
Next Greater Element	Given an array of integers, find the next greater element for each element in the array. If there is no greater element, return -1.	For the array `[2, 1, 2, 4, 3]`, the next greater elements are `[4, 2, 4, -1, -1]`.
Next Smaller Element	Given an array of integers, find the next smaller element for each element in the array. If there is no smaller element, return -1.	For the array `[4, 5, 2, 10, 8]`, the next smaller elements are `[2, 2, -1, 8, -1]`.

Code Template

Initializes variables

result = [-1] * n: Creates a list of the same length as nums, initialized to -1. This will hold the next greater elements.
stack = []: Initializes an empty list to track indices of elements in nums during iteration.

Check for next greater element

Checks if the stack is not empty and if the current element nums[i] is greater than the element at the index on the top of the stack.
If both conditions are true, it means nums[i] is the next greater element for the index at the top of the stack, and we pop indices from the stack until this condition is false.

Append current index to stack

Retrieves the index from the stack and updates the result list with the current element nums[i] as its next greater element.
Adds the current index i to the stack for future comparisons.

def monotonic_stack(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

Common mistakes

Wrong Stack Empty Check

# Wrong: missing stack check
while nums[stack[-1]] < nums[i]:  # Will error on empty stack
# Wrong: wrong order of conditions
while nums[stack[-1]] < nums[i] and stack:  # Will error
# Correct:
while stack and nums[stack[-1]] < nums[i]:  # Check stack first

503. Next Greater Element II

Same template on a circular array: scan 0 .. 2n - 1, use index i % n for values, and only stack.append(i) on the first lap (i < n) so each index appears once.

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack = []

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

        return result

739. Daily Temperatures

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack = []

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

        return result

901. Online Stock Span

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span) pairs
        
    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            prev_price, prev_span = self.stack.pop()
            span += prev_span
            
        self.stack.append((price, span))
        return span

1019. Next Greater Node In Linked List

class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        # Convert linked list to array
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
            
        n = len(nums)
        result = [0] * n
        stack = []  # (index, value) pairs
        
        for i in range(n):
            while stack and stack[-1][1] < nums[i]:
                prev_idx, _ = stack.pop()
                result[prev_idx] = nums[i]
            stack.append((i, nums[i]))
        return result

1475. Final Prices With a Special Discount in a Shop

Next smaller-or-equal to the right: same index stack, compare with <= instead of <, and write price - discount when you pop.

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        result = list(prices)
        stack = []

        for i in range(len(prices)):
            while stack and prices[i] <= prices[stack[-1]]:
                index = stack.pop()
                result[index] = prices[index] - prices[i]
            stack.append(i)

        return result