Monotonic Stack for Next Greater/Smaller Element

1. What is a Monotonic Stack?

As the name suggests, a monotonic stack is a stack where the elements are always maintained in a specific sorted order, either non-decreasing (increasing) or non-increasing (decreasing) from the bottom to the top of the stack.

There are two types:

• Monotonic Increasing Stack: Each new element pushed is greater than or equal to the element at the top of the stack. This structure is ideal for finding the previous/next smaller element.
• Monotonic Decreasing Stack: Each new element pushed is less than or equal to the element at the top of the stack. This is used for finding the previous/next greater element.

Let's watch a short video that introduces this concept and its purpose.

A key takeaway from the video is the tip to store indices in the stack instead of the actual values. Your background in data structures and algorithms should make it clear why this is beneficial: storing indices gives you access to the original values via the input array while also providing positional information (like distance), which is often required in problem variations.

2. The Core Pattern: Next Greater Element

The canonical problem for this pattern is "Next Greater Element" (NGE).

Problem Statement: Given an array nums, for each element nums[i], find the first element to its right that is strictly greater than nums[i]. If no such element exists, the answer for that position is -1.

Example:
For nums = [2, 1, 5, 6, 2, 3], the next greater elements are [5, 5, 6, -1, 3, -1].

From Brute Force to an O(n) Solution

The straightforward approach is to use nested loops: for each element, you scan the rest of the array to its right. This results in an O(n²) time complexity, which is often too slow for interview constraints.

The key insight for an O(n) solution is this: as we iterate through the array, we can use a stack to keep track of the indices of elements for which we have not yet found a next greater element.

Let's walk through the logic using a monotonically decreasing stack.

The Algorithm

1. Initialize an empty stack (to store indices) and a result array of the same size as the input, filled with -1.
2. Iterate through the input array nums from left to right with index i.
3. For each element nums[i]:
   • While the stack is not empty AND the current element nums[i] is greater than the element at the index on top of the stack (nums[stack[-1]]):
     • This means nums[i] is the "next greater element" for the index at stack[-1].
     • Pop the index from the stack: popped_index = stack.pop().
     • Update the result: result[popped_index] = nums[i].
   • After the while loop finishes, push the current index i onto the stack. The elements on the stack will always correspond to values in decreasing order.
4. After the main loop, any indices remaining in the stack have no next greater element, and their entries in result correctly remain -1.

To see this algorithm in action, let's turn back to the AlgoMasterIO video.

For a written explanation and Python implementation, this article is an excellent reference.

3. Common Variations

The beauty of this pattern is its adaptability. By making small tweaks to the logic, you can solve a family of related problems.

• Next Smaller Element: To find the first element to the right that is smaller, you just flip the condition in the while loop: while stack and nums[i] < nums[stack[-1]]. This maintains a monotonically increasing stack.

• Previous Greater/Smaller Element: To find elements to the left, the overall traversal and stack logic remains similar. You still iterate from left to right. However, the meaning of the stack changes slightly. When you are at index i, the elements on the stack are candidates for being the "previous greater/smaller" element.

  Let's take Previous Greater Element as an example:

  1. Iterate i from 0 to n-1.
  2. While the stack is not empty and nums[i] >= nums[stack[-1]], pop from the stack. (You are removing elements that are smaller or equal, because they can't be the "previous greater" element for nums[i]).
  3. After the loop, if the stack is not empty, the index at the top is the answer. result[i] = nums[stack[-1]]. If it's empty, result[i] = -1.
  4. Push i onto the stack.

The article "Monotonic Stack Problems" provides code templates for all four variations.

4. Application: Daily Temperatures

A common interview question that is a thinly veiled "Next Greater Element" problem is LeetCode 739: Daily Temperatures.

Problem: Given an array of integers temperatures, return an array answer where answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0.

This is identical to finding the next greater element, but instead of storing the value, you store the distance between the indices (next_greater_index - current_index).

Let's see the solution to this problem, which directly applies the pattern we just learned.

Conclusion

You have now learned a powerful and efficient pattern for a class of problems that frequently appear in technical interviews. Moving from a brute-force O(n²) solution to an optimized O(n) solution using a monotonic stack demonstrates a deep understanding of both algorithms and data structures.

Key Takeaways:

• A monotonic stack maintains its elements in either increasing or decreasing order.
• It is the go-to pattern for finding the next/previous greater/smaller element in an array in linear time, O(n).
• The core mechanism involves iterating through the array and using the stack to hold indices of elements awaiting their "match." When a new element breaks the stack's monotonic property, you've found the answer for the elements you pop.
• Storing indices on the stack is more flexible than storing values, as it allows for calculating distances or retrieving original values.

In our next lesson, we will introduce the deque (double-ended queue) and use it to solve another high-ROI pattern: the sliding window maximum. This will continue our journey of applying linear data structures to solve complex problems efficiently.