🧱🧱 Monotonic Stack - Guide + List of Problems 🧱🧱
Ezio Super Empath
11135
StackMonotonic StackCareer

Monotonic Stack

Monotonic : A sequence or function that is either entirely non-increasing or entirely non-decreasing.
Stack : A data structure using LIFO (Last In First Out ) strategy.

Is Monotonic Stack a Data Structure ?
No . Its a technique or approach that uses stack data structure , or some other data structure that can simulate stack LIFO behaviour.

What is a Monotonic Stack?
A Monotonic stack is a variation of the traditional stack data structure that maintains either a strictly increasing or strictly decreasing order of elements. Unlike a regular stack, where elements can be inserted and removed freely, a monotonic stack enforces a specific order to its elements.


When to use Monotonic Stack Technique ?
In problems where we need to process

  • Next greater Element
  • Next smaller Element
  • Previous greater Element
  • Previous smaller Element
  • Lexicographically Smallest/Greatest
  • Histogram Related Problems left and right boundaries for each bar

Basic Template :

void monotonicStack(const vector<int>& arr) {
    stack<int> st;
    for (int i = 0; i < arr.size(); ++i) {
			while(STACK NOT EMPTY  &&   st.top() OPERATOR arr[i] && other Logic given in problem ){
					//Extract the stack top
					//POP  the element 
					
					//Use the current element and STACK TOP to update result
					
					}
			
			//Push in stack
    }
	
	//at this point we have a monotonic stack in our hand
}

Types of monotonic stack (Bottom to top)

  • Strictly increasing stack
  • Non-decreasing stack
  • Strictly decreasing stack
  • Non-increasing stack

Problem 1 : ✏️✏️✏️ 739. Daily Temperatures (Next Greater)

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

Approach:

Problem wants us to find the Next Greater Element Index(NGEI) .

Difference of the NGEI and the current index tells the number of days to wait for a warmer day .

For each temperature, we check if it is greater than the temperature of the day represented by the index stored at the top of the stack.
If it is greater, it means we have found a warmer temperature for the day represented by that index. We keep popping elements from the stack until we find a temperature higher than the current temperature or until the stack becomes empty. For each popped element, we update the corresponding answer in the answer array.

Expand to see code 
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        vector<int>res(n,0);
        // find next greeater
        for (int i = 0; i < n; i++) {
            int ele = nums[i];
            while (!st.empty() && ele > nums[st.top()]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i); 
        }
        return res;
    }
};

Problem 2 : ✏️✏️✏️402. Remove K Digits(Constrained Monotonic Stack )

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example: For "1234591234" we delete 9 to make it minimal => 123451234

Key observations:

If the number is increasing in nature at each digit then it is the lowest number .
For each character, it aims to find the next smaller element (digit) to its right.

Constrained monotonic stack: maintains a stack with the constraint of removing a specific number of elements (k) while ensuring a monotonic property.
Explained Solution in Detail

The algorithm compares each character ch with the last character in the ans string(acting as monotonic increasing stack). If ch is smaller than the last character in ans, it means ch is the next smaller element compared to the last element in ans. The algorithm removes elements from string ans until ch becomes the next smaller element

Expand to see code 
class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans="";// this will represent the stack 
        for(auto ch: num){
            while(ans.size() && ch < ans.back() && k){
                ans.pop_back();
                k--;
            }
            if(ans.size()==0 && ch=='0')continue;
            ans.push_back(ch);
        }

        while(ans.size() && k--)ans.pop_back();

        if(ans.size()>0)return ans;
        return "0";//
    }
};

Problem 3 : ✏️✏️✏️ Remove Duplicate Letters

Problem : Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical orderamong all possible results.

Smallest lexicographical order is the hint for using Monotonic Stack.

Monotonic increasing stack is built to ensure that the resulting string is the smallest in lexicographical order among all possible results. The stack is maintained in such a way that it only contains characters in increasing order, ensuring that when a character is added to the stack, it maintains the lexicographical order. Additionally, it also pops elements from the stack when necessary to ensure that the final string is the smallest possible.

Our primary goal is to form a monotonic increasing stack

Expand to see code 
class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<int>st;
        vector<bool>vis(26,false);// CAN ALSO USE AN UNORDERED MAP <char,bool>
        //it is marked true if character is in stack , false otherwise
        vector<int>freq(26,0);// FREQUENCY TELLS IF MORE OCCURENCE COME IN FUTURE
        
        for(auto it: s)
            freq[it-'a']++;

        for(int i=0;i<s.length();i++){
            char ch=s[i];
            freq[ch-'a']--;
            if(vis[ch-'a']==false){
                while(!st.empty() && st.top() > ch && freq[st.top()-'a']>0){
                    vis[st.top()-'a']=false;
                    st.pop();
                }
            vis[ch-'a']=true;
            st.push(ch);
            }
        }
        string res="";
        while (!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Problems List

1. Single Pass

Input Type : Array / Strings

2. Two or more Pass

Input Type : Array / Matrix

3. Monotonic Stack on Linked List

Input Type : Linked List

Summary :

ProblemStack Typeloop condition
next greaterdecreasing (equal allowed)stackTop < current
previous greaterdecreasing (strict)stackTop <= current
next smallerincreasing (equal allowed)stackTop > current
previous smallerincreasing (strict)stackTop >= current

Some other Posts by me :

🔍🔍Binary Search🔍🔍 Summary

💎 💎 PREFIX SUM + HASH-MAP TECHNIQUE 💎💎

🪟Sliding Window🪟 Summary

🚀 🚀Master Tree Patterns 🚀🚀

✅✅Graph - Summary ✅✅

🚀🚀 Backtracking Summary 🚀🚀

Comments (7)