Monotonic Stack
Cheat Sheet
Prime Use Case
Use when you need to find the 'nearest' element (left or right) that satisfies a specific comparison property (e.g., next greater, previous smaller) in linear time.
Critical Tradeoffs
- Time: Amortized O(N) vs O(N^2) brute force
- Space: O(N) to store the stack vs O(1) for brute force
- Input: Works on unsorted data but maintains a 'local' sorted property
Killer Senior Insight
The monotonic stack effectively 'collapses' the search space by discarding elements that can no longer be the 'nearest' answer for any future elements in the iteration.
Recognition
Common Interview Phrases
Common Scenarios
- Daily Temperatures (LeetCode 739)
- Largest Rectangle in Histogram (LeetCode 84)
- Sum of Subarray Minimums
- Online Stock Span
Anti-patterns to Avoid
- Using it for global maximum/minimum queries across the entire array (use a simple variable)
- Using it when the relative order of elements doesn't matter (sorting might be better)
- Attempting to find the K-th largest element (use a Heap or QuickSelect)
The Problem
The Fundamental Issue
Eliminating redundant comparisons in nested loops when searching for boundary conditions in an array.
What breaks without it
Time Limit Exceeded (TLE) on constraints where N > 10^4
Excessive re-scanning of the same elements in a nested O(N^2) approach
Why alternatives fail
Sorting the array destroys the index-based 'nearest' relationship required for these problems
Heaps/Priority Queues provide the global extremum but don't respect the linear positioning of elements
Mental Model
The Intuition
Imagine a line of people of different heights. If a very tall person joins the end of the line, they 'block' the view of everyone shorter than them for anyone looking from the right. The stack only keeps the people who are still 'visible'.
Key Mechanics
Iterate through the array once
While the stack is not empty AND the current element violates the monotonic property compared to the stack top, pop the stack
Process the popped element (this is often where the 'answer' for that element is recorded)
Push the current element (or its index) onto the stack
Framework
When it's the best choice
- When the problem involves 'boundaries' or 'ranges' where an element is the minimum or maximum
- When you need a linear time solution for a problem that looks like it requires nested loops
When to avoid
- When the array is already sorted (a simple pointer or binary search is more efficient)
- When you need to access elements in the middle of the stack (violates LIFO)
Fast Heuristics
Tradeoffs
Strengths
- Reduces O(N^2) problems to O(N) time complexity
- Single pass processing (ideal for streaming data)
- Extremely low constant factor overhead compared to Segment Trees
Weaknesses
- Requires O(N) auxiliary space which can be an issue in memory-constrained environments
- Logic can be counter-intuitive (popping elements to maintain order)
- Difficult to debug due to the 'amortized' nature of the operations
Alternatives
When it wins
When you need to perform range maximum/minimum queries with frequent updates.
Key Difference
O(log N) per query vs O(1) amortized, but supports dynamic updates.
When it wins
When you need to find the maximum/minimum in a fixed-size moving window.
Key Difference
Maintains elements at both ends to handle the window 'sliding' out of range.
When it wins
When the array is static and you need O(1) range minimum queries.
Key Difference
Requires O(N log N) preprocessing and space.
Execution
Must-hit talking points
- Explain that each element is pushed and popped exactly once, leading to O(N) time.
- Mention that storing indices in the stack is usually superior to storing values.
- Discuss how to handle duplicate values (strictly increasing vs non-decreasing).
- Identify the 'contribution' of an element to the final answer during the pop phase.
Anticipate follow-ups
- Q:How would you handle a circular array? (Double the array or use i % n)
- Q:Can you solve this in 2D? (e.g., Largest sub-matrix of 1s)
- Q:What if the data is too large to fit in memory? (External sorting or streaming stack)
Red Flags
Forgetting to push the current element after the while loop.
Why it fails: The current element must be added to the stack to serve as a potential boundary for future elements.
Using the wrong comparison operator (e.g., > instead of >=).
Why it fails: This leads to incorrect handling of duplicate elements, which is a common edge case in histogram problems.
Not clearing the stack at the end of the iteration.
Why it fails: Remaining elements in the stack often represent items that have no 'next greater' element; failing to process them leads to incomplete results.