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 next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

Common mistakes

Wrong Stack Comparison Direction

# Wrong:
while stack and nums[stack[-1]] > nums[i]:  # Finds next smaller element
# Correct:
while stack and nums[stack[-1]] < nums[i]:  # Finds next greater element

Wrong Stack Content Storage

# Wrong: storing values instead of indices
stack.append(nums[i])  # Can't track original positions
result[stack.pop()] = nums[i]  # Will cause error
# Correct:
stack.append(i)  # Store indices to track positions
index = stack.pop()
result[index] = nums[i]

Wrong Result Array Initialization

# Wrong: using empty list or zeros
result = []  # Can't index into empty list
result = [0] * n  # Can't distinguish between actual 0 and no answer
# Correct:
result = [-1] * n  # Use -1 to indicate no greater element found

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

496. Next Greater Element I

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums2)
        result = {}  # map number to its next greater element
        stack = []
        
        # Find next greater element for each number in nums2
        for i in range(n):
            while stack and nums2[stack[-1]] < nums2[i]:
                index = stack.pop()
                result[nums2[index]] = nums2[i]
            stack.append(i)
        # Build result for nums1 using the mapping
        return [result.get(x, -1) for x in nums1]

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

Monotonic Stack

Use Cases

Code Template

Initializes variables

Check for next greater element

Append current index to stack

Common mistakes

Related Problem

Resources