Lets talk about Monotonic Stacks today.

As the name suggests, its a Stack. But what does Monotonic mean ?

In this context it means - either always increasing or always decreasing. The elements in the stack at any given point of time are always in some order.

Types

You would have probably guessed it by now. Monotonic Stack are of 2 types -

1. Monotonic increasing stack
2. Monotonic decreasing stack

depending on whether the elements in the stack are always in increasing or decreasing order.

Problems It Solves

Using a monotonic stack, we can efficiently find the next/previous greater or the next/previous smaller element of any element in an array.

It is able to do that because of its property - elements in the stack are always in the increasing or decreasing order. And if this order is violated at any step, we pop elements from the stack until the order is retained.

Next Smaller Element

In order to implement a monotonic stack in such a way that we get next smaller element for all the elements in the array, we will have to implement a monotonic increasing stack.

Algorithm is simple -

1. Iterate over every element of the array.
2. In each step, check if stack is empty.
3. If not, check whether the element of the array is less than the element represented by the top of the stack.
4. If yes, then pop the top of the stack and record the popped value in a results array against the current index.
5. Again repeat step 3 and 4.

One thing to note - We are not keeping values in stack, rather we are storing indices in the stack.

Here is the code for it -

function nextSmallerElements(arr = []) {
    const stack = [];
    const result = new Array(arr.length).fill(undefined);

    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
            result[stack.pop()] = i;
        }
        stack.push(i);
    }

    return result.map(k => k && arr[k]);
}

So, if you now pass an array into the above function, it’ll look like this -

const arr1 = [1, 2, 7, 8, 3, 5];
console.log(nextSmallerElements([...arr1]));
// This will print  [undefined, undefined, 3, 3, undefined, undefined ]

In this way, you can get the next smaller element of each of the element of the array. Neat, right ?

Previous Smaller Element

Mmm, well no need to complicate this particular problem. We just need to reverse the array being sent to the nextSmallerElements() function, and then reverse the output array as well.

function previousSmallerElements(arr = []) {
    return nextSmallerElements(arr.reverse()).reverse();
}

So, if you now pass an array into the above function, it’ll look like this -

const arr1 = [1, 2, 7, 8, 3, 5];
console.log(previousSmallerElements([...arr1]));
// This will print [ undefined, 1, 2, 7, 2, 3 ]

Next Greater Element

You must have guessed it by now. In order to find out next greater element of all the elements in the array, we now need to implement a monotonic decreasing stack.

The algorithm is the same as Next Smaller Element approach, with one simple change, in step 3. of the algorithm mentioned above -

If not, check whether the element of the array is GREATER than the element represented by the top of the stack.

function nextGreaterElements(arr = []) {
    const stack = [];
    const result = new Array(arr.length).fill(undefined);

    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
            result[stack.pop()] = i;
        }
        stack.push(i);
    }

    return result.map(k => k && arr[k]);
}

So, if you now pass an array into the above function, it’ll look like this -

const arr1 = [1, 2, 7, 8, 3, 5];
console.log(nextGreaterElements([...arr1]));
// This will print [ 2, 7, 8, undefined, 5, undefined ]

So simple, right ?

And finally…

Previous Greater Element

Again, the same logic as that of Previous Smaller Element, but now with nextGreaterElements() function.

function previousGreaterElements(arr = []) {
    return nextGreaterElements(arr.reverse()).reverse();
}

So, if you now pass an array into the above function, it’ll look like this -

const arr1 = [1, 2, 7, 8, 3, 5];
console.log(previousGreaterElements([...arr1]));
// This will print [ undefined, undefined, undefined, undefined, 8, 8 ]

Complexity Analysis

To understand the importance of this algorithm, we need to understand the complexities of solving such problems with a brute force approach first -

With the Brute force approach, finding the next/previous smaller/greater element would have taken O(n^2) time as the solution would involve iterating over all the elements n times.

But, with monotonic stack approach, the same time complexity would be now O(n), as we are iterating over all elements just once. Space complexity will also be O(n), as max space that can be utilized by the stack would be n only.

Leetcode Problems

There are a few Leetcode problems which you can solve to get more familiar with the Monotonic stack approach -

• 496 Next Greater Element I
• 739 Daily Temperatures
• 84 Largest Rectangle in Histogram

Happy Coding!