🧩 Python DSA Patterns — Monotonic Stack & Queue 📉🐍

Many array problems look hard not because of logic — but because of repeated comparisons.

Monotonic stacks and queues solve this by keeping elements in a specific order, allowing us to answer range and dominance questions efficiently.

This pattern turns several O(n²) brute-force problems into clean O(n) solutions.

🧠 What Is a Monotonic Structure?

A monotonic stack or queue maintains elements in either:

• Increasing order, or
• Decreasing order

This ordering allows instant access to:

• Next greater / smaller element
• Previous greater / smaller element
• Maximum / minimum in a sliding window

Each element is added once and removed once — guaranteeing linear time.

📝 Next Greater Element (Monotonic Decreasing Stack)

We keep a stack of indices whose next greater element hasn’t been found yet.

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

    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    print("Next Greater Elements:", result)

💡 Why it works:

Once an element finds its next greater value, it never needs to be checked again.

📝 Previous Smaller Element (Monotonic Increasing Stack)

Here, the stack maintains increasing order so the top always gives the previous smaller value.

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

    for i in range(len(nums)):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        result[i] = nums[stack[-1]] if stack else -1
        stack.append(i)

    print("Previous Smaller Elements:", result)

💡 Key idea:

Elements that can never serve as a “previous smaller” are removed early.

📝 Daily Temperatures (Monotonic Stack)

For each day, find how many days it takes to encounter a warmer temperature.

def daily_temperatures(temps):
    stack = []
    result = [0] * len(temps)

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

    print("Days Until Warmer Temperature:", result)

💡 Insight:

This is a direct application of Next Greater Element with distance tracking.

📝 Sliding Window Maximum (Monotonic Queue)

A monotonic queue keeps the maximum element always at the front of the window.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()
    result = []

    for i in range(len(nums)):
        if dq and dq[0] == i - k:
            dq.popleft()

        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    print("Sliding Window Maximum:", result)

💡 Why deque:

We need fast removals from both ends.

🧠 Where This Pattern Is Used

• 📊 Next / Previous Greater or Smaller problems
• 🌡️ Daily Temperatures
• 📈 Stock Span
• 🪟 Sliding Window Maximum / Minimum
• 🧱 Histogram & range dominance problems

Once learned, this pattern appears everywhere.

✅ Takeaway

• Monotonic stacks and queues enforce order
• Each element is processed once → O(n)
• Store indices, not values
• Choose:
  • Stack → next/previous problems
  • Queue → sliding window problems

This is one of the most high-impact patterns in DSA.

🏋️ Practice Problems

1. Next Greater Element I & II
2. Daily Temperatures
3. Stock Span
4. Sliding Window Maximum
5. Largest Rectangle in Histogram

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns