Monotonic Stack/Deque Intro

If you'd prefer a video:

The word "monotonic" means a list or a function is either always increasing, or always decreasing. In that case, a "monotonic stack" or a "monotonic deque" is a stack or a deque that has this property.

Monotonic stack is like a regular stack with one key distinction in the push operation: Before we push a new element onto the stack, we first check if adding it breaks the monotonic condition. If it does, then we pop the top element off the stack until pushing the new element no longer breaks the monotonic condition.

Below is a graphical explanation of the idea. It is a monotonic stack that is decreasing, but the same idea can also be applied to deque and other monotonic data structures.

Example implementation

Below is an example implementation of a monotonic stack.

1def mono_stack(insert_entries):
2    stack = []
3    for entry in insert_entries:
4        # The monotonic property can only break if and only if the container
5        # is not empty and the last item, compared to the entry, breaks
6        # the property. While that is true, we pop the top item.
7        while stack and stack[-1] <= entry:
8            stack.pop()
9            # Do something with the popped item here
10        stack.append(entry)
11

1public static void monoStack(List<Integer> insertEntries) {
2    ArrayList<Integer> stack;
3    for (int entry : insertEntries) {
4        // The monotonic property can only break if and only if the container
5        // is not empty and the last item, compared to the entry, breaks
6        // the property. While that is true, we pop the top item.
7        while (!stack.isEmpty() && stack.get(stack.size() - 1) <= entry) {
8            stack.remove(stack.size() - 1);
9            // Do something with the popped item here
10        }
11        stack.add(entry);
12    }
13}
14

1function monoStack(insertEntries) {
2    const stack = [];
3    for (let entry of insertEntries) {
4        // The monotonic property can only break if and only if the container
5        // is not empty and the last item, compared to the entry, breaks
6        // the property. While that is true, we pop the top item.
7        while (stack.length > 0 && stack[stack.length - 1] <= entry) {
8            stack.pop();
9            // Do something with the popped item here
10        }
11        stack.push(entry);
12    }
13}
14

1void mono_stack(std::vector<int> insert_entries) {
2    std::vector<int> stack;
3    for (int entry : insert_entries) {
4        // The monotonic property can only break if and only if the container
5        // is not empty and the last item, compared to the entry, breaks
6        // the property. While that is true, we pop the top item.
7        while (!stack.empty() && stack.back() <= entry) {
8            // Do something with the top item in stack here
9            stack.pop_back();
10        }
11        stack.push_back(entry);
12    }
13}
14

Note that when we use a monotonic stack to solve real interview problems, we often store the index of the element in the stack instead of the value. This is because we can always look up the value from the original array and by storing the indices we can calculate the distance between elements in the original array.

A monotonic stack stores both the position and value. The indices of the elements in the monotonic stack are always increasing. The values of the elements are either monotonically increasing or decreasing.

Applications of Monotonic Stack/Deque

There are a few interesting properties of a monotonic stack/deque that we can utilize in certain types of questions.

By definition, the monotonic property of this data structure is always maintained, so you know the entries in the stack/deque is sorted. Furthermore, we know that items that get popped during the insertion always sorted because the insertion breaks the monotonic property, so if a particular item didn't get popped this way, it is because the monotonic property was maintained for that item.

For example, in the example above, consider the number 3 at index 0. When it gets popped, 6 was inserted and it breaks the monotonic property, but every insertion before did not break the property for 3. Therefore, we know that the next larger or equal number for 3 is 6.

Next Largest or Smallest Element in a List

As shown above, this method is effective when you need to determine the next larger or smaller member for each element in a list, as it can naturally be determined when you insert element into the stack in order. The overall complexity of this algorithm is O(n), because each item in the list is inserted and popped at most once.

If there are other restrictions, such as the next larger/smaller member must be within a certain distance, then we can use a deque instead, and pop from the end of the deque when the range is exceeded.

For an example, see Daily Temperatures.

Maximum or Minimum Element in a Sliding Window

Furthermore, because the stack/deque is monotonic, you can easily access the maximum/minimum element by looking at the start of the stack/queue. This means that for a sliding window, we can easily keep track of its maximum/minimum element. When we insert an item from one side, we perform the monotonic insertion method on the deque, and when we remove an item from the other side, we simply pop the item on the other side if the index matches.

For an example, see Sliding Window Maximum.