straight to the point , the idea i had behind this notion page is when i was solving stack questions with reference to striver’s A-Z sheet i noticed a lot of patterns here and there and just wanted to document it and as you have visited the page,if you like solving DSA then i guess you will like to know this perspective too.

Firstly going with stack

am gonna ‘continue’ (coders will get this) the implementation part of stack as you all know its LIFO, memory structure,keeps track of elements or indices which arrays cant blah blah…

soo now while solving DSA especially company based we will come across NGE(Next greater element),PGE(previous greater element),NSE,PSE like many many times.

Here’s the code:

//NSE
//optimised one
vector<int>nextse(vector<int>&arr){
     stack<int>s;  //storing indices
     int n = arr.size();
     vector<int>nse(n); //this imp or else runtime error
     for(int i=n-1;i>=0;i--){
        while(!s.empty() && arr[s.top()]>arr[i]){
           s.pop();
        }
        if(s.empty()) nse[i]=-1; //no nse
        else nse[i]=s.top();
        
        s.push(i); //dont forget this, again runtime error
     }
     return nse;
}

//PSE
//optimal
vector<int>prevse(vector<int>&arr){
    stack<int>s;
    int n = arr.size();
    vector<int>pse(n);
    for(int i=0;i<n;i++){
    while(!s.empty() && arr[s.top()]>=arr[i]{
        s.pop();
    }
    if(s.empty()) pse[i]=-1;
    else pse[i]=s.top();
    
    s.push(i);
   }
   return pse;
}

And for NGE and PGE its the same but just you pop a diff niche of elements from the stack:

arr[s.top()]<arr[i] //nge
arr[s.top()]<=arr[i] //pge

Soo coming back to my observation after solving Sum of subarray minimums,Sum of subarray maximums,Largest histogram rectangle,Stock span i came to realise that the problem can be approached in two ways within this optimal world of NGE,NSE,PSE and PGE.

SPAN