When solving sequence-based problems—like finding the next greater element, stock span, or calculating sliding window maximum—efficiency is paramount. Many of these problems involve comparing elements across a sequence, and a brute-force approach often leads to nested loops with a costly O(n^2) time complexity.
Enter the monotonic stack: a powerful data structure that simplifies and accelerates sequence-based algorithms, turning what might seem like an intimidating problem into an elegant and efficient solution. In this blog post, we’ll explore why monotonic stacks are the go-to choice for sequence-based problems and how they work.
What is a Monotonic Stack?
A monotonic stack is a special type of stack that maintains a specific order among its elements:
• Monotonic Increasing Stack: Elements are stored in ascending order from bottom to top.
• Monotonic Decreasing Stack: Elements are stored in descending order from bottom to top.
Example:
• You have a monotonically increasing stack: [1, 5, 8, 15, 23].
• Now, you want to add 14 to the stack:
• Since 15 and 23 are greater than 14, you remove them (because they’d make the order incorrect if 14 came after them).
• After adding 14, the stack becomes: [1, 5, 8, 14].
Monotonic stacks are ideal for problems where you need to find the “next” element based on specific criteria, like the next greater element. They are also effective for dynamically maintaining the maximum or minimum element in a changing window. In complex problems, they are often combined with other techniques as part of a larger algorithm.
How Monotonic Stacks Supercharge Algorithm Efficiency
1. Efficient Element Processing
Monotonic stacks process each element in the sequence exactly once:
• Push: Add an element to the stack.
• Pop: Remove elements that no longer meet the monotonic condition.
• This ensures an overall time complexity of O(n) because each element is pushed and popped only once.
2. Dynamic Relevance Maintenance
In sequence-based problems, many elements become irrelevant as you move through the input. Monotonic stacks discard these irrelevant elements dynamically:
Imagine a group of people standing in a line, and your goal is to figure out the next taller person for each individual.
As you walk through the line, you look for the next taller person for each individual.
Some people in the line are shorter than the current person you’re processing. These shorter individuals become irrelevant.
You keep a stack of relevant people as you walk down the line:
• If the next person is taller than the one on top of the stack, you remove (pop) the shorter person from the stack.
• Why? The shorter person is no longer needed because the taller person will be the “next taller” for all subsequent individuals.
Daily Temperatures Problem Explained
The Daily Temperatures Problem is a well-known, sequence-based problem where you are asked to determine, for each day, how many days you have to wait until a warmer temperature occurs. If no such day exists, you should return 0.
import java.util.Stack;
public class StockSpan {
public static int[] calculateSpan(int[] prices) {
int n = prices.length;
int[] span = new int[n];
Stack<Integer> stack = new Stack<>(); // Stack to store indices of prices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[i] >= prices[stack.peek()]) {
stack.pop();
}
span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return span;
}
}How Monotonic Stack Works Here:
1. Use a monotonic decreasing stack to track indices of temperatures.
2. As you process each temperature:
• Pop indices from the stack if the current temperature is warmer.
• For each popped index, calculate the difference between the current index and the popped index to find the waiting days.
3. Push the current index onto the stack to process later.
Conclusion
Monotonic stacks are a powerful tool in algorithm design, especially for sequence-based problems where maintaining order or efficiently finding the “next” or “previous” element is critical. By dynamically removing irrelevant elements and preserving a monotonic order, they enable efficient solutions to problems that might otherwise require nested loops or excessive comparisons. Whether you’re solving the next greater element problem, managing stock spans, or working with histograms, monotonic stacks offer both simplicity and performance. Mastering this technique not only strengthens your problem-solving toolkit but also deepens your understanding of efficient algorithm design.
