Monotonic Stack

🏔️ The Monotonic Stack: Your Magic Sorting Helper

A Story About Standing in Line

Imagine you’re at a theme park. You’re standing in a line, and you want to know: “Who is the next person taller than me?”

You could look at everyone behind you, one by one. But that takes forever!

What if you had a magic helper that instantly tells you the answer?

That’s what a Monotonic Stack does for numbers!

🎢 What is a Monotonic Stack?

A Monotonic Stack is a special stack where elements are always in order:

• Decreasing: Each new item is smaller (or equal)
• Increasing: Each new item is bigger (or equal)

Think of it like a slide at a playground:

• On a decreasing slide, you only go DOWN
• On an increasing slide, you only go UP

# A decreasing stack example
stack = [9, 7, 5, 3]  # Always going down!

# If we try to add 6...
# We must remove 5 and 3 first!
# Result: [9, 7, 6]

🔍 The Next Greater Element Pattern

The Big Question

For each number in a list, find the first number to the right that is bigger.

The Story

Imagine people standing in a line by height. Each person asks: “Who is the first person taller than me behind me?”

Heights: [4, 2, 7, 3, 1, 5]

Person 4 looks back → sees 7 (TALLER!)
Person 2 looks back → sees 7 (TALLER!)
Person 7 looks back → nobody taller → -1
Person 3 looks back → sees 5 (TALLER!)
Person 1 looks back → sees 5 (TALLER!)
Person 5 looks back → nobody → -1

Answer: [7, 7, -1, 5, 5, -1]

The Magic Code

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

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

    return result

# Example
print(next_greater([4, 2, 7, 3, 1, 5]))
# Output: [7, 7, -1, 5, 5, -1]

Why Does This Work?

graph TD
    A["Start with empty stack"] --> B["Look at each number"]
    B --> C{Is current number<br>bigger than stack top?}
    C -->|Yes| D["Pop! Found next greater"]
    D --> C
    C -->|No| E["Push current to stack"]
    E --> B

The stack keeps “waiting” numbers. When a bigger number comes, all the smaller waiting numbers found their answer!

🌡️ Daily Temperatures

The Problem

You have temperatures for each day. For each day, find: “How many days until a warmer day?”

The Story

Imagine you’re waiting for summer. Each cold day, you ask: “When will it get warmer?”

Temps: [73, 74, 75, 71, 69, 72, 76, 73]

Day 0 (73°): Wait 1 day for 74°
Day 1 (74°): Wait 1 day for 75°
Day 2 (75°): Wait 4 days for 76°
Day 3 (71°): Wait 2 days for 72°
Day 4 (69°): Wait 1 day for 72°
Day 5 (72°): Wait 1 day for 76°
Day 6 (76°): Never warmer → 0
Day 7 (73°): Never warmer → 0

Answer: [1, 1, 4, 2, 1, 1, 0, 0]

The Solution

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []  # stores indices

    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day
        stack.append(i)

    return result

# Example
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]

Visual Walkthrough

Step 1: stack = [0]     (73 waiting)
Step 2: 74 > 73, pop!   result[0] = 1
        stack = [1]     (74 waiting)
Step 3: 75 > 74, pop!   result[1] = 1
        stack = [2]     (75 waiting)
Step 4: 71 < 75
        stack = [2, 3]  (75, 71 waiting)
Step 5: 69 < 71
        stack = [2, 3, 4]
Step 6: 72 > 69, pop!   result[4] = 1
        72 > 71, pop!   result[3] = 2
        stack = [2, 5]
Step 7: 76 > 72, pop!   result[5] = 1
        76 > 75, pop!   result[2] = 4
        stack = [6]
Step 8: 73 < 76
        stack = [6, 7]

🏛️ Largest Rectangle in Histogram

The Problem

You have bars of different heights. Find the biggest rectangle you can draw.

The Story

Imagine building a swimming pool between buildings. You want the BIGGEST pool possible!

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

        ▓▓
     ▓▓ ▓▓
     ▓▓ ▓▓    ▓▓
▓▓   ▓▓ ▓▓ ▓▓ ▓▓
▓▓ ▓▓ ▓▓ ▓▓ ▓▓ ▓▓
─────────────────
 2  1  5  6  2  3

The biggest rectangle has area = 10
(height 5, width 2)

Why Monotonic Stack?

The key insight: For each bar, we need to know:

• How far LEFT can it extend?
• How far RIGHT can it extend?

A bar can extend until it meets a shorter bar!

The Solution

def largest_rectangle(heights):
    stack = []
    max_area = 0

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

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

    return max_area

# Example
print(largest_rectangle([2, 1, 5, 6, 2, 3]))
# Output: 10

Step by Step Magic

graph TD
    A["For each bar"] --> B{Current shorter<br>than stack top?}
    B -->|Yes| C["Pop and calculate area"]
    C --> D["Width = current - popped index"]
    D --> E["Update max area"]
    E --> B
    B -->|No| F["Push current bar"]
    F --> A
    A --> G["Process remaining in stack"]

Visual Example

heights = [2, 1, 5, 6, 2, 3]

i=0: Push (0, 2)
     stack = [(0, 2)]

i=1: 1 < 2, pop!
     Area = 2 * 1 = 2
     Push (0, 1)
     stack = [(0, 1)]

i=2: 5 > 1
     Push (2, 5)
     stack = [(0,1), (2,5)]

i=3: 6 > 5
     Push (3, 6)
     stack = [(0,1), (2,5), (3,6)]

i=4: 2 < 6, pop!
     Area = 6 * 1 = 6
     2 < 5, pop!
     Area = 5 * 2 = 10 ← MAX!
     Push (2, 2)
     stack = [(0,1), (2,2)]

i=5: 3 > 2
     Push (5, 3)
     stack = [(0,1), (2,2), (5,3)]

Final processing:
     (5, 3): Area = 3 * 1 = 3
     (2, 2): Area = 2 * 4 = 8
     (0, 1): Area = 1 * 6 = 6

Maximum Area = 10

🎯 Next Smaller Element (Bonus Pattern!)

The same idea works for finding smaller elements too!

Just flip the comparison:

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

    for i in range(n):
        # Pop LARGER elements (flipped!)
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# Example
print(next_smaller([4, 2, 7, 3, 1, 5]))
# Output: [2, 1, 3, 1, -1, -1]

🧠 The Golden Pattern

All monotonic stack problems follow this template:

def monotonic_stack_template(nums):
    result = [default_value] * len(nums)
    stack = []  # Usually stores indices

    for i in range(len(nums)):
        while stack and condition(nums[i], nums[stack[-1]]):
            popped_idx = stack.pop()
            # Do something with popped element
            result[popped_idx] = calculate(...)
        stack.append(i)

    return result

When to Use What?

🚀 Why is it Fast?

Without monotonic stack: O(n²)

• For each element, scan all others

With monotonic stack: O(n)

• Each element pushed once
• Each element popped once
• Total: 2n operations = O(n)

It’s like having a super-organized helper that remembers exactly what you need!

🎮 Quick Recap

1. Monotonic Stack = A stack where elements stay in order (always increasing OR always decreasing)

2. Next Greater Element = Use decreasing stack, pop when you find something bigger

3. Daily Temperatures = Same as Next Greater, but track the day difference

4. Largest Rectangle = Pop shorter bars, calculate width using indices

5. The Magic = Each element enters and leaves the stack exactly once = O(n)!

💡 Remember This

“The monotonic stack is like a bouncer at a club. It only lets numbers in if they follow the rules. When a rule-breaker arrives, it kicks out everyone who doesn’t belong!”

Now you’re ready to tackle any monotonic stack problem! 🎉