Monotonic Stack Problems
Hello everyone, we all know STACK but What is a Monotonic Stack?
Monotonic Stack is a special variation of the typical data structure Stack and appeared in many interview questions.As its name shows, monotonic stack contains all features that a normal stack has and its elements are all monotonic decreasing or increasing.
It just uses some ingenious logic to keep the elements in the stack orderly (monotone increasing or monotone decreasing) after each new element putting into the stack.
Name of Problem on Leetcode: Next Greater Element I
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
Constraints: All integers in an Array are positive and unique.
Let’s take an example:
Given Array, arr : [7,2,1,6,9,5,4]Let’s say the Length of Array is L, here L = 7
We have to find the next greater element of each element of an array, If there is no next greater element for a given element, then return -1 for that element.
First, create an empty stack of size L, say S1={}.
Push the first element of an array in Stack S1, S1 = {7}
Now, as we start inserting other elements of the array in the stack we have to keep in mind that the inserting element should be smaller than the top element of the stack, if it is greater, then pop all elements from the stack which are smaller then inserting element and map them with inserting element as their next greater element.
This way we will get the mapping of each element of an array with its next greater element and elements which get remain in Stack S1 to have no next greater element present, so we return -1 for those elements.
Time Complexity : O(N)Space Complexity : O(N)
Other Variants of this problem :
1. Next Smaller Element
[In this, we will pop from the stack when we encounter the next small element, other things will be similar as of Next Greater Element]
2. Previous Greater Element
[In this, we are going to traverse the array in reverse order and pop from the stack as we encounter the next greater element]
3. Previous Smaller Element
[In this, we are going to traverse the array in reverse order and pop from the stack as we encounter the next smaller element]
References:
1. Monotonic Stack by Yang Zhou
2. Monotone Stack (Leetcode Next greater / smaller )
3. Java Solution using Monotonic Stack
4. Java Solution without using Stack
To connect or collaborate ping me:
LinkedIn
Twitter
GitHub