Monotonic Stack

Today let us learn about monotonic stacks and their usage.

A monotonic stack is one in which the elements of the stack are always increasing or decreasing. This ensures that the stack is always sorted in some order. Some interesting applications of monotonic stacks are to

• Find the next smaller or greater element in an array
• Find the previous smaller or greater element in an array
• Find the minimum or maximum element in a sliding window etc.

Let’s take a look at an example problem below.

Find the next greater element in an array

The next greater of an element X in an array is the first greater element to the right side of X. For example:

[1, 2, 3, 4]

• Next greater element (1) => 2
• Next greater element (2) => 3
• Next greater element (3) => 4

In this problem, we can use a monotonic stack to push elements into and keep popping the elements as long as the top most element has a value smaller than the current element whose next greater element we want to find. That’s a mouthful, so let’s look at an example!

We have the following array.

Input: [1, 3, 4, 2, 5] and here’s an array of the next first greater elements to the right of each element in the array.

Output: [3, 4, 5, 5, -1] (-1 when no next greater element exists)

Algorithm:

• Iterate the given array from i = 0 to i = N – 1.
• Push the element array[i] in the monotonic stack if either the stack is empty or the top of stack > array[i]. We are thereby building a monotonic stack decreasing from the bottom to top.
• In this process, we have to pop the elements in stack if they are lesser than array[i] which is the first greater element found to the right of the popped one.

Look at how the stack and the mapping changes as we iterate the array in the following diagram.

Finally push 5.

Time Complexity: O(N) where N is the size of the array that is iterated. This is because we iterate the array only once and each element is pushed and popped exactly once.

Space Complexity: O(N) since the mapping and the stack will contain at most N elements.

Code:

In the following code nums1 contains the elements whose next greater element should be found in nums2.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num_to_next_greater_mapping = collections.defaultdict(lambda: -1)
        mono_stack = []
        
        for index, val in enumerate(nums2):
            if mono_stack and val > mono_stack[-1]:
                while mono_stack and mono_stack[-1] < val:
                    num_to_next_greater_mapping[mono_stack[-1]] = val
                    mono_stack.pop(-1)
            mono_stack.append(val)
            
        results = []
        for n in nums1:
            results.append(num_to_next_greater_mapping[n])
            
        return results
            

Stay tuned for more of these problems in this space.