Monotonic Stack Applications

Welcome back to our journey through fundamental data structures. In our previous lessons, we explored how the LIFO (Last-In, First-Out) principle of stacks helps validate nested structures and how the FIFO (First-In, First-Out) nature of queues can be implemented efficiently.

Today, we will dive into a more advanced and powerful application of the stack: the monotonic stack. This is not a new data structure, but a specific way of using a regular stack to solve a whole class of problems that often appear in technical interviews. Your learning outcome for this lesson is to use a monotonic stack to find the next greater or smaller element for every position in an array. This pattern is a prime example of how choosing the right data structure can transform an inefficient, brute-force algorithm into a sleek, linear-time solution.

The "Next Greater Element" Problem

Let's begin with a classic problem. Given an array of numbers, for each element, we want to find the first element to its right that is larger. If no such element exists, we can use a placeholder like -1.

Consider the array [2, 1, 5, 3, 4].

• For 2, the next greater element is 5.
• For 1, the next greater element is 5.
• For 5, there is no greater element to its right, so the answer is -1.
• For 3, the next greater element is 4.
• For 4, there is no greater element to its right, so the answer is -1.

The final result would be [5, 5, -1, 4, -1].

Your first instinct, drawing on your extensive programming experience, might be a brute-force approach: for each element i, iterate through all elements j to its right until you find one where nums[j] > nums[i]. This involves a nested loop, leading to an $O(n^2)$ time complexity. While correct, this can be too slow for large inputs, a common scenario in interview challenges.

The image below perfectly contrasts this repetitive, brute-force method with the efficient, single-pass approach we're about to learn.

Our goal is to achieve the $O(n)$ solution on the right.

Introducing the Monotonic Stack

A monotonic stack is a stack where the elements are always in a sorted order, either strictly increasing or strictly decreasing. We enforce this property during insertion. When we push a new element, we first pop any elements from the top of the stack that would violate the monotonic property.

For the "Next Greater Element" problem, we will use a stack that maintains a monotonically decreasing sequence of values (from bottom to top). The core idea is that the stack will hold elements that are still "waiting" for their next greater element to appear.

When we iterate through the array and encounter a new number, current, we compare it with the element at the top of the stack:

• If current is greater than the stack's top element, it means we have found the "next greater element" for that top element. We can pop the element from the stack, record its result, and repeat this process until the stack is empty or its new top is no longer smaller than current.
• After processing all the smaller elements, current is pushed onto the stack to await its own next greater element.

This "one element resolves many" principle is the key to the pattern's efficiency.

The following resource provides a clear definition and an excellent step-by-step walkthrough.

A Visual Walkthrough

To solidify this process, let's look at a visual representation. The diagram below illustrates the state of the input array, the stack (storing indices), and the result array at each step of the process for nums = [2, 1, 5, 3, 4]. This matches the logic you just read about.

Let's trace the first few steps from the diagram:

1. i=0, current=2: The stack is empty. We push index 0. Stack: [0]. Result: [-1, -1, -1, -1, -1].
2. i=1, current=1: The top of the stack holds index 0, and nums[0] is 2. Since 1 < 2, the decreasing order is maintained. We push index 1. Stack: [0, 1].
3. i=2, current=5: The top of the stack is index 1, nums[1] is 1. Since 5 > 1, we have found the next greater element for index 1. We pop 1 and set result[1] = 5. The stack now is [0].
   • We check again. The new top is index 0, nums[0] is 2. Since 5 > 2, we've also found the next greater element for index 0. We pop 0 and set result[0] = 5.
   • The stack is now empty. We push the current index 2. Stack: [2]. Result: [5, 5, -1, -1, -1].

This process continues until all elements are processed.

Why is it O(n)? An Amortized Argument

You might be concerned about the while loop inside the main for loop. Doesn't that risk $O(n^2)$ complexity? This is where the concept of amortized analysis, which we touched on in the last lesson, becomes crucial.

Think about it this way: each element's index is pushed onto the stack exactly once. It is also popped from the stack at most once. Over the entire execution of the algorithm, there will be a total of n pushes and at most n pops. The work done by the inner while loop is not performed n times for each outer loop iteration; rather, its total work is spread out across the entire run. Therefore, the total time complexity is $O(n)+O(n)=O(n)$.

The resource you read earlier provides an excellent, succinct explanation of this.

From Theory to Code: A Full TypeScript Implementation

Now, let's look at a complete implementation. While the left-to-right traversal we've seen is very intuitive, a right-to-left traversal is equally valid and sometimes simpler to code. The following resource implements the right-to-left strategy to solve LeetCode's "Next Greater Element I" problem.

This problem is a slight variation: you're given two arrays, nums1 and nums2, where nums1 is a subset of nums2. You need to find the next greater element in nums2 for each element from nums1. The core logic remains the same, but it uses a hash map to store the results for nums2 before looking them up for nums1.

Notice that in the right-to-left approach, when you are at an element x, the answer is whatever is left on top of the stack after you have popped all smaller elements. This is a subtle but important difference from the left-to-right approach, where the element causing the pop is the answer. Both are valid; the key is understanding the pattern.

Generalizing the Pattern: The Four Variants

The true power of this pattern lies in its versatility. By making small tweaks to the traversal direction and the comparison operator, you can solve four related problems:

1. Next Greater Element (Traverse left-to-right, pop while stack.top < current)
2. Previous Greater Element (Traverse left-to-right, pop while stack.top <= current, answer is stack.top before pushing)
3. Next Smaller Element (Traverse left-to-right, pop while stack.top > current)
4. Previous Smaller Element (Traverse left-to-right, pop while stack.top >= current, answer is stack.top before pushing)

Recognizing that a problem is one of these four variants is a major step toward solving it. The table in the following resource summarizes this beautifully. It also touches on when to use strict (>) versus non-strict (>=) comparisons, a key detail for more advanced problems.

Conclusion

You have just learned one of the most elegant patterns in algorithm design. By enforcing a simple ordering property on a stack, we unlocked a linear-time solution to a problem that seemed to require quadratic time. This transition from brute-force to a structure-aware, optimized solution is a skill you will use time and again.

Here are the key takeaways from today's lesson:

• Monotonic Stack: A stack that maintains its elements in a sorted (increasing or decreasing) order.
• Core Application: Efficiently finding the next/previous greater/smaller element for every item in a sequence.
• Linear Time Complexity: The O(n) performance comes from an amortized analysis; each element is pushed and popped at most once.
• Store Indices: It's generally best to store indices on the stack, not values, to retain positional information.
• Versatility: The pattern can be adapted to four different problems by changing the traversal direction and comparison operator.

In our next lesson, we will continue our exploration of stacks by tackling another classic problem: evaluating postfix (or Reverse Polish Notation) expressions. This will further solidify your understanding of how stacks manage operands and operators in a structured way.