Common Stack Patterns

Recognizing a stack as the right data structure is only the first step. The next step is knowing which pattern to apply. This lesson covers the two most important stack patterns in coding interviews: the monotonic stack and iterative depth-first traversal. Each solves a specific class of problems that would otherwise require significantly more expensive approaches.

Monotonic stack

The monotonic stack pattern maintains a stack in sorted order, either strictly increasing or strictly decreasing, as we scan through an array. When an incoming element violates the sort order, we pop elements off the stack until the order is restored, processing each popped element as we go. This gives us $O(n)$ solutions to problems that would otherwise require $O(n^2)$ ...