Monotonic Stack
Overview
A Monotonic Stack is not a new data structure; it is a pattern applied to a standard Stack. 'Monotonic' means either entirely non-increasing or entirely non-decreasing.
In a Monotonic Stack, we enforce a strict rule before pushing a new element: we pop elements from the top of the stack until the stack maintains its sorted order.
This pattern is the ultimate weapon for a very specific class of array problems: finding the Next Greater Element or Next Smaller Element in O(N) time. A naive nested loop solution would take O(N^2) time, but a monotonic stack processes every element exactly twice (once pushed, once popped), resulting in strict O(N) time complexity.
Syntax
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class MonotonicStack {
// Problem: For every element, find the next element to its right that is larger.
// Example: [2, 1, 2, 4, 3] -> [4, 2, 4, -1, -1]
public static int[] nextGreaterElement(int[] nums) {
int[] result = new int[nums.length];
Arrays.fill(result, -1); // Default if no greater element exists
// Stack will store INDICES, not values, to maintain a monotonically decreasing stack
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
// While current element is GREATER than the element at the top of the stack...
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
// We found the 'Next Greater Element' for the index at the top of the stack!
int prevIndex = stack.pop();
result[prevIndex] = nums[i];
}
// Push current index onto the stack
stack.push(i);
}
return result;
}
}Common Pitfalls
- Storing values instead of indices. A very common mistake is pushing
nums[i]onto the stack instead ofi. If you only push values, when you find a greater element, you don't know where to put it in the result array! Always push indices. - Using the wrong inequality. If you want the 'Next Greater' element, use a strictly decreasing stack (
nums[i] > nums[stack.peek()]). If you want the 'Next Smaller', use an increasing stack (nums[i] < nums[stack.peek()]). - Forgetting to handle elements left in the stack. After the loop finishes, any indices remaining in the stack have no 'Next Greater' element. You should initialize the result array with
-1(or whatever default) beforehand to handle this automatically.
Interview Questions
while loop inside a for loop?Because every element is pushed onto the stack exactly once, and popped off the stack at most once. Over the course of the entire for loop, the inner while loop will only execute a maximum of N times total. Therefore, the total operations scale linearly with N, making it O(N).
Instead of iterating from left-to-right (0 to N-1), you iterate from right-to-left (N-1 down to 0). The stack logic remains exactly the same. When iterating backwards, finding the 'next' element in the iteration means finding the 'previous' element in the physical array.
Real-World Example
Stock Market algorithms use monotonic stacks to calculate 'Span'. If you have an array of daily stock prices, you want to know for each day how many consecutive days prior the price was lower or equal. A monotonic stack calculates this for the entire history in strict O(N) time, rather than comparing every day against every previous day (O(N^2)).
public int[] calculateStockSpans(int[] prices) {
int[] spans = new int[prices.length];
Deque<Integer> stack = new ArrayDeque<>(); // Stores indices
for (int i = 0; i < prices.length; i++) {
// Pop all previous days where the price was LOWER than today
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
}
// Span is current day minus the index of the last day that was HIGHER
spans[i] = stack.isEmpty() ? (i + 1) : (i - stack.peek());
stack.push(i);
}
return spans;
}Check Your Knowledge
Test your understanding of Monotonic Stack with these quick questions.