Monotonic Stack

🏔️ The Tower Watchers: Mastering the Monotonic Stack

Imagine you’re standing in a city of towers, each one a different height. You want to find the first taller tower to your right. How would you do it efficiently?

🌟 What is a Monotonic Stack?

Think of a monotonic stack like a special line at an amusement park.

The Rule: Only people of increasing (or decreasing) height can stay in line. When a taller person arrives, shorter people must leave!

Stack (decreasing): [8, 5, 3, 2]
                     ↑
New element: 6 arrives!

6 > 2? Yes! Pop 2
6 > 3? Yes! Pop 3
6 > 5? Yes! Pop 5
6 > 8? No! Stop.

Stack now: [8, 6]

Simple Definition: A monotonic stack is a stack where elements are always in sorted order (either all increasing or all decreasing from bottom to top).

🎯 The Next Greater Element Pattern

The Story

Imagine you’re a tower watcher. For each tower, you want to know: “Which is the first taller tower to my right?”

Brute Force (The Slow Way): For each tower, look at every tower to the right. This takes O(n²) time. Too slow!

Smart Way (Monotonic Stack): Process towers from right to left. Keep a stack of “candidate” taller towers.

How It Works

function nextGreaterElements(arr) {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack = []; // stores indices

  // Process from right to left
  for (let i = n - 1; i >= 0; i--) {
    // Remove smaller elements
    while (stack.length > 0 &&
           arr[stack[stack.length - 1]] <= arr[i]) {
      stack.pop();
    }

    // Stack top is next greater
    if (stack.length > 0) {
      result[i] = arr[stack[stack.length - 1]];
    }

    // Add current index
    stack.push(i);
  }

  return result;
}

Visual Example

Array: [4, 5, 2, 10, 8]

Processing right to left:

i=4: arr[4]=8, stack=[]
     → No next greater. result[4]=-1
     → Push 4. stack=[4]

i=3: arr[3]=10, stack=[4]
     → 10 > 8? Pop 4. stack=[]
     → No next greater. result[3]=-1
     → Push 3. stack=[3]

i=2: arr[2]=2, stack=[3]
     → 2 > 10? No.
     → Next greater = 10. result[2]=10
     → Push 2. stack=[3,2]

i=1: arr[1]=5, stack=[3,2]
     → 5 > 2? Pop 2. stack=[3]
     → 5 > 10? No.
     → Next greater = 10. result[1]=10
     → Push 1. stack=[3,1]

i=0: arr[0]=4, stack=[3,1]
     → 4 > 5? No.
     → Next greater = 5. result[0]=5
     → Push 0. stack=[3,1,0]

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

Next Smaller Element

Same idea, but flip the comparison!

function nextSmallerElements(arr) {
  const n = arr.length;
  const result = new Array(n).fill(-1);
  const stack = [];

  for (let i = n - 1; i >= 0; i--) {
    // Remove LARGER elements (opposite!)
    while (stack.length > 0 &&
           arr[stack[stack.length - 1]] >= arr[i]) {
      stack.pop();
    }

    if (stack.length > 0) {
      result[i] = arr[stack[stack.length - 1]];
    }

    stack.push(i);
  }

  return result;
}

🌡️ Daily Temperatures

The Problem

You have a list of daily temperatures. For each day, find how many days until a warmer day.

Input: [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0]

Day 0 (73°): Next warmer is Day 1 (74°). Wait = 1 day. Day 2 (75°): Next warmer is Day 6 (76°). Wait = 4 days.

The Solution

This IS the Next Greater Element pattern! But we track indices to calculate the gap.

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = []; // stores indices

  for (let i = n - 1; i >= 0; i--) {
    // Pop cooler or equal days
    while (stack.length > 0 &&
           temperatures[stack[stack.length-1]]
             <= temperatures[i]) {
      stack.pop();
    }

    // Calculate days to wait
    if (stack.length > 0) {
      result[i] = stack[stack.length - 1] - i;
    }

    stack.push(i);
  }

  return result;
}

Step-by-Step Walkthrough

Temps: [73, 74, 75, 71, 69, 72, 76, 73]
         0   1   2   3   4   5   6   7

i=7: temp=73, stack=[]
     → Push 7. result[7]=0

i=6: temp=76, stack=[7]
     → 76>73? Pop 7. stack=[]
     → Push 6. result[6]=0

i=5: temp=72, stack=[6]
     → 72>76? No.
     → result[5]=6-5=1 ✓
     → Push 5. stack=[6,5]

i=4: temp=69, stack=[6,5]
     → 69>72? No.
     → result[4]=5-4=1 ✓

i=3: temp=71, stack=[6,5,4]
     → 71>69? Pop 4. stack=[6,5]
     → 71>72? No.
     → result[3]=5-3=2 ✓

...and so on!

🏛️ Largest Rectangle in Histogram

The Problem

Given bars of different heights, find the largest rectangle you can draw.

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

    █
   ██
   ██
   ██ █
 █ ████
 ██████

Answer: 10 (5×2 rectangle using heights 5 and 6)

Why Monotonic Stack?

For each bar, we need:

1. Left boundary: First shorter bar to the left
2. Right boundary: First shorter bar to the right

Width = right - left - 1 Area = height × width

The Magic Solution

function largestRectangle(heights) {
  const n = heights.length;
  const stack = [];
  let maxArea = 0;

  for (let i = 0; i <= n; i++) {
    // Use 0 as sentinel at the end
    const currHeight = i === n ? 0 : heights[i];

    while (stack.length > 0 &&
           currHeight < heights[stack[stack.length-1]]) {

      const height = heights[stack.pop()];
      const width = stack.length === 0
        ? i
        : i - stack[stack.length-1] - 1;

      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}

Visual Breakdown

Heights: [2, 1, 5, 6, 2, 3]
Indices:  0  1  2  3  4  5

Processing:

i=0: h=2, stack=[]
     → Push 0. stack=[0]

i=1: h=1, stack=[0]
     → 1 < 2? Yes! Pop 0
     → Area = 2 × 1 = 2
     → Push 1. stack=[1]

i=2: h=5, stack=[1]
     → 5 < 1? No. Push 2. stack=[1,2]

i=3: h=6, stack=[1,2]
     → 6 < 5? No. Push 3. stack=[1,2,3]

i=4: h=2, stack=[1,2,3]
     → 2 < 6? Pop 3. Area = 6×1 = 6
     → 2 < 5? Pop 2. Area = 5×2 = 10 🎉
     → 2 < 1? No. Push 4. stack=[1,4]

i=5: h=3, stack=[1,4]
     → Push 5. stack=[1,4,5]

i=6: h=0 (sentinel), stack=[1,4,5]
     → Pop 5. Area = 3×1 = 3
     → Pop 4. Area = 2×4 = 8
     → Pop 1. Area = 1×6 = 6

Maximum Area = 10 ✅

🧠 The Pattern Summary

graph TD
    A["Monotonic Stack Problems"] --> B{What do you need?}
    B -->|Next Greater| C["Decreasing Stack"]
    B -->|Next Smaller| D["Increasing Stack"]
    B -->|Range/Area| E["Track Boundaries"]
    C --> F["Pop smaller elements"]
    D --> G["Pop larger elements"]
    E --> H["Calculate on pop"]

When to Use Monotonic Stack

✅ Finding next greater/smaller element ✅ Problems about “first X to the left/right” ✅ Histogram/rectangle problems ✅ Temperature/stock price patterns

Time Complexity

Always O(n)! Each element is pushed and popped at most once.

🎮 Quick Reference

The Secret: The stack stores candidates. When a new element arrives, we eliminate impossible candidates!

🚀 Key Takeaways

1. Monotonic = Sorted Order - Stack stays in increasing or decreasing order

2. O(n) Magic - Each element pushed/popped once total

3. Direction Matters - Left-to-right vs right-to-left depends on the problem

4. Three Core Problems:

   • Next Greater/Smaller Element
   • Daily Temperatures
   • Largest Rectangle in Histogram

You now have the power to see patterns in towers, temperatures, and histograms. Go build something amazing! 🏆