Monotonic Stack Patterns: Complete Reference¶

# Canonical: Store indices
stack = []  # stack of indices
for i, val in enumerate(arr):
    while stack and arr[stack[-1]] < val:
        idx = stack.pop()
        # arr[idx] found its next greater at position i
    stack.append(i)  # Push index, not value

def next_greater_element(nums: list[int]) -> list[int]:
    """
    For each element, find the next greater element to its right.
    Returns -1 if no such element exists.

    Algorithm:
    - Maintain a monotonically decreasing stack (by value)
    - When current element > stack top, stack top found its NGE
    - Each element is pushed once and popped at most once → O(n)

    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n  # Default: no next greater
    stack = []  # Stack of indices, values are decreasing

    for i in range(n):
        # Pop all elements smaller than current (they found their NGE)
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]  # or result[idx] = i for index
        stack.append(i)

    return result

def previous_smaller_element(nums: list[int]) -> list[int]:
    """
    For each element, find the previous smaller element to its left.
    Returns -1 if no such element exists.

    Algorithm:
    - Maintain a monotonically increasing stack (by value)
    - For each element, pop until we find a smaller element
    - The stack top (if exists) is the previous smaller element

    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Stack of indices, values are increasing

    for i in range(n):
        # Pop elements >= current (they can't be PSE for future elements)
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()

        # Stack top (if exists) is the previous smaller element
        if stack:
            result[i] = nums[stack[-1]]  # or stack[-1] for index

        stack.append(i)

    return result

def next_greater_variants(nums: list[int]) -> tuple[list[int], list[int], list[int]]:
    """
    Compute NGE returning value, index, and distance.
    """
    n = len(nums)
    nge_value = [-1] * n     # The value of next greater element
    nge_index = [-1] * n     # The index of next greater element
    nge_distance = [0] * n   # Distance to next greater element
    stack = []

    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            nge_value[idx] = nums[i]
            nge_index[idx] = i
            nge_distance[idx] = i - idx
        stack.append(i)

    return nge_value, nge_index, nge_distance

# Strict: Find next STRICTLY greater (not equal)
while stack and nums[stack[-1]] < nums[i]:  # < means strictly less
    # ...

# Non-strict: Find next greater or equal
while stack and nums[stack[-1]] <= nums[i]:  # <= includes equal
    # ...

def next_greater_circular(nums: list[int]) -> list[int]:
    """
    Find next greater element in circular array.

    Algorithm:
    - Traverse array twice (indices 0 to 2n-1)
    - Use modulo to wrap around: actual_index = i % n
    - Only push indices during first pass (i < n)
    - Second pass only resolves remaining elements

    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        actual_idx = i % n

        # Pop elements that found their circular NGE
        while stack and nums[stack[-1]] < nums[actual_idx]:
            idx = stack.pop()
            result[idx] = nums[actual_idx]

        # Only push during first pass to avoid duplicate processing
        if i < n:
            stack.append(actual_idx)

    return result

def largest_rectangle_two_pass(heights: list[int]) -> int:
    """
    Largest rectangle using two passes for left/right boundaries.

    Time: O(n), Space: O(n)
    """
    n = len(heights)
    left_smaller = [-1] * n   # Index of first smaller bar to left
    right_smaller = [n] * n   # Index of first smaller bar to right

    # Pass 1: Find left boundaries (previous smaller)
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left_smaller[i] = stack[-1] if stack else -1
        stack.append(i)

    # Pass 2: Find right boundaries (next smaller)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right_smaller[i] = stack[-1] if stack else n
        stack.append(i)

    # Compute maximum area
    max_area = 0
    for i in range(n):
        width = right_smaller[i] - left_smaller[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)

    return max_area

def largest_rectangle_single_pass(heights: list[int]) -> int:
    """
    Largest rectangle using single pass with sentinel.

    The sentinel (0 at end) forces all remaining bars to be popped,
    completing their rectangle computation.

    Time: O(n), Space: O(n)
    """
    heights = heights + [0]  # Sentinel: forces final flush
    stack = [-1]  # Virtual left boundary
    max_area = 0

    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# With duplicates: [2, 2, 2]
# Using > (strict): Each bar stops at its immediate neighbor
# Using >= (non-strict): Each bar extends through equal-height bars

while stack[-1] != -1 and heights[stack[-1]] >= h:  # >= for duplicates

def maximal_rectangle(matrix: list[list[str]]) -> int:
    """
    Find largest rectangle of 1s in binary matrix.

    Algorithm:
    - Build histogram row by row
    - Each cell's height = consecutive 1s above (including current)
    - Apply largest_rectangle_in_histogram to each row

    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:
        # Update histogram
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0

        # Find largest rectangle in current histogram
        max_area = max(max_area, largest_rectangle_single_pass(heights[:]))

    return max_area

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    For each day, find how many days until a warmer temperature.
    This is the distance to the next greater element.

    Time: O(n), Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack of indices, temperatures are decreasing

    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            result[idx] = i - idx  # Distance to next greater
        stack.append(i)

    return result

class StockSpanner:
    """
    Online computation of stock span.
    Span = number of consecutive days with price <= today's price.

    Key insight: Span includes the current day plus all days
    that were "dominated" by previous greater prices.

    Stack stores (price, span) pairs.
    """
    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1  # Current day counts

        # Pop and accumulate spans of dominated days
        while self.stack and self.stack[-1][0] <= price:
            _, prev_span = self.stack.pop()
            span += prev_span

        self.stack.append((price, span))
        return span

def sum_of_subarray_minimums(arr: list[int]) -> int:
    """
    Sum of minimums of all subarrays.

    Algorithm:
    - For each element, find left/right boundaries (previous/next smaller)
    - Use asymmetric tie-breaking to avoid double-counting duplicates:
      - Left boundary: strictly smaller (<)
      - Right boundary: smaller or equal (<=)

    Time: O(n), Space: O(n)
    """
    MOD = 10**9 + 7
    n = len(arr)

    # left[i] = distance to previous smaller element
    # right[i] = distance to next smaller or equal element
    left = [0] * n
    right = [0] * n

    # Compute left boundaries (previous strictly smaller)
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:  # >= for strict <
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # Compute right boundaries (next smaller or equal)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:  # > for <=
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    # Sum contributions
    result = 0
    for i in range(n):
        result = (result + arr[i] * left[i] * right[i]) % MOD

    return result

def sum_of_subarray_ranges(nums: list[int]) -> int:
    """
    Sum of (max - min) for all subarrays.

    = Sum of all subarray maximums - Sum of all subarray minimums

    Use dual stacks: one for max contribution, one for min contribution.

    Time: O(n), Space: O(n)
    """
    n = len(nums)

    def sum_of_extremes(compare_greater: bool) -> int:
        """Compute sum of subarray max (if True) or min (if False)."""
        left = [0] * n
        right = [0] * n
        stack = []

        # Comparison functions for max vs min
        def dominates(a, b):
            return a > b if compare_greater else a < b

        def dominates_or_equal(a, b):
            return a >= b if compare_greater else a <= b

        # Left boundaries
        for i in range(n):
            while stack and dominates_or_equal(nums[i], nums[stack[-1]]):
                stack.pop()
            left[i] = i - stack[-1] if stack else i + 1
            stack.append(i)

        # Right boundaries
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and dominates(nums[i], nums[stack[-1]]):
                stack.pop()
            right[i] = stack[-1] - i if stack else n - i
            stack.append(i)

        return sum(nums[i] * left[i] * right[i] for i in range(n))

    sum_max = sum_of_extremes(True)
    sum_min = sum_of_extremes(False)
    return sum_max - sum_min

def trap(height: list[int]) -> int:
    """
    Calculate total trapped rainwater.

    Algorithm:
    - Maintain a monotonically decreasing stack
    - When we see a taller bar, we've found a valley
    - Pop the bottom of the valley, compute water trapped
    - Water width = current_index - left_wall_index - 1
    - Water height = min(left_wall, right_wall) - bottom_height

    Time: O(n), Space: O(n)
    """
    stack = []  # Stack of indices, heights are decreasing
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()

            if not stack:
                break  # No left wall, water flows out

            left_wall_idx = stack[-1]
            left_wall_height = height[left_wall_idx]
            right_wall_height = h
            bottom_height = height[bottom]

            width = i - left_wall_idx - 1
            bounded_height = min(left_wall_height, right_wall_height) - bottom_height
            water += width * bounded_height

        stack.append(i)

    return water

def remove_k_digits(num: str, k: int) -> str:
    """
    Remove k digits to create the smallest possible number.

    Algorithm:
    - Maintain monotonically increasing stack (greedy best prefix)
    - Pop larger digits when a smaller digit is seen (local optimality)
    - Handle leading zeros and remaining k

    Time: O(n), Space: O(n)
    """
    stack = []

    for digit in num:
        # Pop larger digits if we can still remove (k > 0)
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # If k > 0, remove from the end (stack is increasing, end is largest)
    if k > 0:
        stack = stack[:-k]

    # Remove leading zeros and handle empty result
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

def remove_duplicate_letters(s: str) -> str:
    """
    Remove duplicate letters to get lexicographically smallest result.
    Each character must appear exactly once.

    Additional constraints:
    - Track last occurrence of each character
    - Only pop if the character appears later

    Time: O(n), Space: O(26) = O(1)
    """
    last_occurrence = {c: i for i, c in enumerate(s)}
    stack = []
    in_stack = set()

    for i, c in enumerate(s):
        if c in in_stack:
            continue

        # Pop if current is smaller and popped char appears later
        while stack and stack[-1] > c and last_occurrence[stack[-1]] > i:
            in_stack.remove(stack.pop())

        stack.append(c)
        in_stack.add(c)

    return ''.join(stack)

# Left boundary: strictly smaller (exclusive)
while stack and arr[stack[-1]] >= arr[i]:  # >=

# Right boundary: smaller or equal (inclusive)
while stack and arr[stack[-1]] > arr[i]:   # >

# Canonical: Store indices
stack.append(i)
value = arr[stack[-1]]
distance = i - stack[-1]

# Anti-pattern: Store values (loses position information)
stack.append(arr[i])  # Can't compute distances!

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

def prev_smaller(arr):
    n, result, stack = len(arr), [-1] * len(arr), []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        result[i] = arr[stack[-1]] if stack else -1
        stack.append(i)
    return result

def largest_rectangle(heights):
    heights, stack, max_area = heights + [0], [-1], 0
    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            max_area = max(max_area, height * (i - stack[-1] - 1))
        stack.append(i)
    return max_area

def trap(height):
    stack, water = [], 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if stack:
                w = i - stack[-1] - 1
                bounded = min(height[stack[-1]], h) - height[bottom]
                water += w * bounded
        stack.append(i)
    return water

def sum_subarray_mins(arr):
    n, MOD = len(arr), 10**9 + 7
    left, right, stack = [0]*n, [0]*n, []
    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)
    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)
    return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD