name: Monotonic Stack
slug: monotonic-stack
difficulty_level: 3
pattern_type: data_structure
display_order: 15

description: >
  Maintain a stack where elements are always in sorted order (either increasing or
  decreasing). This enables efficient solutions for "next greater element" problems
  by leveraging the stack's ability to track candidates that might be the answer
  for future elements.

when_to_use: |
  - Next greater/smaller element
  - Previous greater/smaller element
  - Largest rectangle in histogram
  - Daily temperatures
  - Stock span problems

metaphor: |
  Imagine standing in a line of people of varying heights, all facing forward.
  You want to know who's the next taller person for each person in line. The
  trick: as you walk backward through the line, keep track of "potentially
  useful" tall people. When you encounter someone taller than people you're
  tracking, those shorter people will never be the answer—remove them. The
  remaining stack always contains candidates in decreasing height order.

  Another analogy: a bouncer at a club with height requirements. As people line
  up, anyone shorter than the person in front can be removed from consideration—
  they'll never be visible from the front.

core_concept: |
  A **monotonic stack** maintains elements in sorted order by popping elements
  that violate the ordering when pushing new ones:

  - **Monotonically decreasing**: Pop elements smaller than current before pushing
  - **Monotonically increasing**: Pop elements larger than current before pushing

  The key insight is that when we pop an element, we've found its "next
  greater/smaller"—it's the current element we're about to push. The stack
  efficiently tracks candidates that might be answers for future elements.

  **Pattern recognition:**
  - "Next greater" → decreasing stack (pop when current > top)
  - "Next smaller" → increasing stack (pop when current < top)
  - "Previous greater/smaller" → process elements and query stack before pushing

visualization: |
  **Next Greater Element:**

  ```
  Array: [4, 5, 2, 10, 8]
  Find next greater element for each

  Process right to left (or left to right with index tracking):

  Process 8:  stack=[]        → no greater, push 8
              stack=[8]       → answer[4] = -1

  Process 10: stack=[8]       → 10 > 8, pop 8
              stack=[]        → no greater, push 10
              stack=[10]      → answer[3] = -1

  Process 2:  stack=[10]      → 2 < 10, don't pop
              stack=[10,2]    → answer[2] = 10

  Process 5:  stack=[10,2]    → 5 > 2, pop 2
              stack=[10]      → 5 < 10, don't pop
              stack=[10,5]    → answer[1] = 10

  Process 4:  stack=[10,5]    → 4 < 5, don't pop
              stack=[10,5,4]  → answer[0] = 5

  Result: [5, 10, 10, -1, -1]
  ```

  **Largest Rectangle in Histogram:**

  ```
  Heights: [2, 1, 5, 6, 2, 3]

  Use increasing stack (pop when current < top)
  When popping, calculate rectangle with popped height as the smallest bar.

  Process each bar:
  - 2: push (0,2)
  - 1: 1 < 2, pop (0,2) → width=1, area=2×1=2
       push (0,1) [take popped index]
  - 5: push (2,5)
  - 6: push (3,6)
  - 2: 2 < 6, pop (3,6) → width=1, area=6×1=6
       2 < 5, pop (2,5) → width=2, area=5×2=10
       push (2,2)
  - 3: push (5,3)
  - end: pop remaining, calculate areas

  Max area = 10
  ```

code_template: |
  def next_greater_element(nums: list[int]) -> list[int]:
      """Find next greater element for each position."""
      n = len(nums)
      result = [-1] * n
      stack = []  # Stack of indices

      for i in range(n):
          # Pop elements smaller than current
          while stack and nums[stack[-1]] < nums[i]:
              idx = stack.pop()
              result[idx] = nums[i]

          stack.append(i)

      return result


  def next_smaller_element(nums: list[int]) -> list[int]:
      """Find next smaller element for each position."""
      n = len(nums)
      result = [-1] * n
      stack = []

      for i in range(n):
          # Pop elements larger than current
          while stack and nums[stack[-1]] > nums[i]:
              idx = stack.pop()
              result[idx] = nums[i]

          stack.append(i)

      return result


  def daily_temperatures(temperatures: list[int]) -> list[int]:
      """Days until warmer temperature."""
      n = len(temperatures)
      result = [0] * n
      stack = []  # Stack of indices

      for i in range(n):
          while stack and temperatures[stack[-1]] < temperatures[i]:
              idx = stack.pop()
              result[idx] = i - idx  # Days difference

          stack.append(i)

      return result


  def largest_rectangle_histogram(heights: list[int]) -> int:
      """Largest rectangle area in histogram."""
      stack = []  # Stack of (index, height)
      max_area = 0

      for i, h in enumerate(heights):
          start = i

          while stack and stack[-1][1] > h:
              idx, height = stack.pop()
              max_area = max(max_area, height * (i - idx))
              start = idx  # This index can extend back

          stack.append((start, h))

      # Process remaining in stack
      for idx, height in stack:
          max_area = max(max_area, height * (len(heights) - idx))

      return max_area


  def stock_span(prices: list[int]) -> list[int]:
      """Days since last higher price (inclusive of today)."""
      n = len(prices)
      result = [0] * n
      stack = []  # Stack of indices

      for i in range(n):
          while stack and prices[stack[-1]] <= prices[i]:
              stack.pop()

          # Span = distance to previous higher (or from start)
          result[i] = i - stack[-1] if stack else i + 1

          stack.append(i)

      return result

recognition_signals:
  - "next greater element"
  - "next smaller element"
  - "previous greater"
  - "daily temperatures"
  - "stock span"
  - "largest rectangle"
  - "histogram"
  - "trapping rain water"
  - "132 pattern"
  - "buildings with ocean view"

common_mistakes:
  - title: Wrong comparison direction
    description: |
      Using `<` when you should use `>` (or vice versa) results in the wrong
      type of monotonic stack.
    fix: |
      Remember: "next greater" needs decreasing stack, so pop when `nums[top] < current`.
      "Next smaller" needs increasing stack, so pop when `nums[top] > current`.

  - title: Storing values instead of indices
    description: |
      Storing just values makes it impossible to calculate distances (like
      "how many days until...").
    fix: |
      Store indices in the stack. You can always access `nums[stack[-1]]` for
      the value when needed.

  - title: Not processing remaining stack elements
    description: |
      Elements left in the stack after processing all input have no "next
      greater/smaller" in the array.
    fix: |
      After the main loop, process remaining elements. For histogram problems,
      their rectangle extends to the end. For "next greater," their answer is -1.

  - title: Off-by-one with span calculations
    description: |
      Forgetting whether to include the current element in span calculations
      gives wrong results.
    fix: |
      For span problems, if stack is empty, span = i + 1 (from beginning).
      If stack has elements, span = i - stack[-1] (not +1 because previous
      greater is exclusive).

variations:
  - name: Next greater element
    description: |
      Find the first element to the right that is greater than current.
      Decreasing monotonic stack.
    example: "Next Greater Element I/II, Daily Temperatures"

  - name: Next smaller element
    description: |
      Find the first element to the right that is smaller than current.
      Increasing monotonic stack.
    example: "Next Smaller Element"

  - name: Previous greater/smaller
    description: |
      Query the stack before pushing to find the previous greater/smaller.
      The top of stack is the answer.
    example: "Stock Span, Buildings With Ocean View"

  - name: Largest rectangle
    description: |
      Use increasing stack. When popping, calculate area using popped height
      and width from popped index to current index.
    example: "Largest Rectangle in Histogram, Maximal Rectangle"

  - name: Trapping rain water
    description: |
      Can use monotonic stack to track left boundaries, calculating trapped
      water when finding right boundary. (Alternative: two-pointer approach)
    example: "Trapping Rain Water"

related_patterns:
  - two-pointers
  - sliding-window

prerequisite_patterns: []

visualization_examples:
  - id: largest-rectangle-histogram
    title: "Largest Rectangle in Histogram"
    input:
      heights: [2, 1, 5, 6, 2, 3]
    code: |
      def largest_rectangle(heights):
          stack = []  # (index, height)
          max_area = 0

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

          for idx, height in stack:
              max_area = max(max_area, height * (len(heights) - idx))

          return max_area
    steps:
      - id: step-1
        description: "Goal: Find the largest rectangle that fits in this histogram. Each bar's height is shown, and we want to find the biggest rectangular area."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: default }
              - { value: 1, state: default }
              - { value: 5, state: default }
              - { value: 6, state: default }
              - { value: 2, state: default }
              - { value: 3, state: default }
        variables:
          question: "What's the largest rectangle?"
          max_area: 0

      - id: step-2
        description: "We scan left to right. Bar 0 (height 2) could be the shortest bar in some rectangle. Push it to stack. Format: h:height @start_index."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: active }
              - { value: 1, state: default }
              - { value: 5, state: default }
              - { value: 6, state: default }
              - { value: 2, state: default }
              - { value: 3, state: default }
            pointers:
              i: 0
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:2 @0", state: active }
        variables:
          max_area: 0

      - id: step-3
        description: "Bar 1 (height 1) is SHORTER than bar 0 (height 2). Bar 0's rectangle can't extend further right! Pop it and calculate: width=1, area=2x1=2."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: comparing }
              - { value: 1, state: active }
              - { value: 5, state: default }
              - { value: 6, state: default }
              - { value: 2, state: default }
              - { value: 3, state: default }
            pointers:
              i: 1
            rectangle:
              startIndex: 0
              endIndex: 0
              height: 2
              state: comparing
              label: "Area: 2"
          stack (h:height @start):
            type: stack
            values: []
        variables:
          max_area: 2
          calculation: "height(2) × width(1) = 2"

      - id: step-4
        description: "Now push bar 1 (height 1). Since bar 0 was popped, bar 1's rectangle can extend back to index 0. Stack stores (0, 1)."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: active }
              - { value: 5, state: default }
              - { value: 6, state: default }
              - { value: 2, state: default }
              - { value: 3, state: default }
            pointers:
              i: 1
            maxArea: 2
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:1 @0", state: active }
        variables:
          max_area: 2
          insight: "Height 1 can extend back to index 0!"

      - id: step-5
        description: "Bar 2 (height 5) is taller than bar 1. Taller bars might extend further right, so push it. Bar 3 (height 6) is also taller — push it too."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: default }
              - { value: 5, state: active }
              - { value: 6, state: active }
              - { value: 2, state: default }
              - { value: 3, state: default }
            pointers:
              i: 3
            maxArea: 2
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:6 @3", state: active }
              - { value: "h:5 @2", state: active }
              - { value: "h:1 @0", state: default }
        variables:
          max_area: 2
          stack_note: "Stack keeps increasing heights (bottom to top)"

      - id: step-6
        description: "Bar 4 (height 2) is SHORTER than bar 3 (height 6). Pop bar 3: width=1, area=6x1=6. Still shorter than bar 2 (height 5), pop it: width=2, area=5x2=10!"
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: default }
              - { value: 5, state: comparing }
              - { value: 6, state: comparing }
              - { value: 2, state: active }
              - { value: 3, state: default }
            pointers:
              i: 4
            rectangle:
              startIndex: 2
              endIndex: 3
              height: 5
              state: found
              label: "Area: 10"
            maxArea: 10
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:1 @0", state: default }
        variables:
          max_area: 10
          calculation: "height(5) × width(2) = 10"

      - id: step-7
        description: "Push bar 4 at index 2 (it extends back to where bar 2 was). Bar 5 (height 3) is taller, so push it too."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: default }
              - { value: 5, state: visited }
              - { value: 6, state: visited }
              - { value: 2, state: active }
              - { value: 3, state: active }
            pointers:
              i: 5
            maxArea: 10
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:3 @5", state: active }
              - { value: "h:2 @2", state: active }
              - { value: "h:1 @0", state: default }
        variables:
          max_area: 10
          note: "h:2 starts @2 because it extends back"

      - id: step-8
        description: "Done scanning! Process remaining stack: bar 5 (height 3) extends from index 5 to end (width 1), area=3. Bar 4 (height 2) extends from 2 to end (width 4), area=8."
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: visited }
              - { value: 5, state: visited }
              - { value: 6, state: visited }
              - { value: 2, state: comparing }
              - { value: 3, state: comparing }
            rectangle:
              startIndex: 2
              endIndex: 5
              height: 2
              state: comparing
              label: "Area: 8"
            maxArea: 10
          stack (h:height @start):
            type: stack
            values:
              - { value: "h:1 @0", state: default }
        variables:
          max_area: 10
          remaining: "Still processing stack..."

      - id: step-9
        description: "Bar 1 (height 1) extends from index 0 to end (width 6), area=6. The largest rectangle has area 10 — the one spanning bars 2-3 with height 5!"
        structures:
          heights:
            type: histogram
            bars:
              - { value: 2, state: visited }
              - { value: 1, state: visited }
              - { value: 5, state: found }
              - { value: 6, state: found }
              - { value: 2, state: visited }
              - { value: 3, state: visited }
            rectangle:
              startIndex: 2
              endIndex: 3
              height: 5
              state: found
              label: "Max: 10"
            maxArea: 10
          stack (h:height @start):
            type: stack
            values: []
        variables:
          max_area: 10
          answer: "Largest rectangle = 10"
