Explain Monotonic Stack Pattern.

Monotonic Stack Pattern is a stack-based algorithmic approach that maintains elements in a sorted (either non-decreasing or non-increasing) order to efficiently find next or previous greater/smaller elements.

When to Use

Use the monotonic stack pattern for problems like Next Greater Element, Daily Temperatures, or Largest Rectangle in Histogram. It’s perfect for optimizing brute-force comparisons into linear-time solutions by maintaining a predictable order of elements.

Example

In Daily Temperatures, you can maintain a decreasing stack of indices. When a warmer temperature appears, pop cooler ones to find how many days to wait.

Want to level up?

Explore Grokking Data Structures & Algorithms for Coding Interviews, Grokking System Design Fundamentals, Grokking the Coding Interview, or practice with Mock Interviews with ex-FAANG engineers to accelerate your learning.

Why Is It Important

This pattern improves performance from O(n²) to O(n), since each element is pushed and popped only once. It’s a cornerstone in algorithmic optimization and commonly tested in top tech interviews.

Interview Tips

When faced with “next greater/smaller element” or “span” problems, mention the O(n) complexity and your reasoning for choosing an increasing vs decreasing stack.

Trade-offs

It uses extra O(n) space for the stack but drastically improves time efficiency—ideal for handling large datasets.

Pitfalls

Avoid confusing stack direction (increasing vs decreasing). Handle duplicate elements and edge cases carefully to avoid logic errors.