Monotonic Stack Deep-Dive

I'm going to explain the concept, then immediately test your understanding with questions. This is interactive - not a lecture.

1. What is a Monotonic Stack?

A monotonic stack is a stack that maintains a specific order (either all increasing or all decreasing) as you push/pop elements.

Key insight: When you encounter an element that would "break" the order, you pop elements until the order is restored before pushing the new element.

Example - Monotonic Increasing Stack:

Process: [3, 1, 4, 2]

Step 1: Push 3 → Stack: [3] Step 2: 1 < 3 (breaks increasing) → Pop 3, Push 1 → Stack: [1] Step 3: 4 > 1 (maintains) → Push 4 → Stack: [1, 4] Step 4: 2 < 4 (breaks) → Pop 4, Push 2 → Stack: [1, 2]

Simple rule. That's it.

For "next SMALLER" problems:

• Pop when current is smaller
• Stack ends up in decreasing order (top to bottom)

For "next GREATER" problems:

• Pop when current is greater
• Stack ends up in increasing order (top to bottom)

def nextSmaller(arr): result = [-1] * len(arr) # Default: no answer found stack = [] # Store indices (NOT values - I'll explain why)

for i in range(len(arr)):
    # While current element "triggers" a pop
    while stack and arr[i] < arr[stack[-1]]:
        popped_index = stack.pop()
        result[popped_index] = arr[i]  # ← "RECORD ANSWER"

    stack.append(i)  # Push current index

return result

---

## **Let me trace this with `[4, 2, 1, 5, 3]`:**