Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
How to identify stack questions?
1. Time Complexity reduced from O(n^2) to O(n) (Generally)
2. Brute Force is of the type:
for( int i = 0 to i = n) :
for (int j dependent on i) :
end
endPattern 1: Monotonic Increasing / Decreasing Based Questions
Q1. Next Greater Element to the Right (NGER)
Input: N = 4, arr[] = [1 3 2 4]
Output: 3 4 4 -1
Approach:
For next greater to the right we travel from the left and we check while the stack top is less/equal we pop and finally we push the incoming element. We push the stack top to the vector and while returning we reverse the vector as we traveled from the last.
vector<int> NGER(vector<int> arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = n - 1 ; i >= 0 ; i-- ){
while(st.size() > 0 && st.top() <= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(arr[i]) ;
}
reverse(v.begin() , v.end()) ;
return v ;
}Q2) Next Greater Element to the Right- 2
Approach: We find NGER of the bigger array.
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// size of nums2 > nums 1
vector<int> query = NGER(nums2) ;
vector<int> ans ;
// key : nums2 , value : NGE
unordered_map<int, int> mpp ;
for(int i = 0 ; i < nums2.size() ; i++ ){
mpp[nums2[i]] = query[i] ;
}
for(int i = 0 ; i < nums1.size() ; i++ ){
ans.push_back(mpp[nums1[i]]) ;
}
return ans ;
}Q3) Next Greater Element to the Right in a Circular Array
Approach: Already fill the stack in the reverse direction and then use the same approach.
By doing this we actually have the element on the stack that would have been on the left side of the array.
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> st ;
vector<int> v ;
int n = nums.size() ;
for(int i = n - 1 ; i >= 0 ; i-- ){
st.push(nums[i]) ;
}
for(int i = n - 1 ; i >= 0 ; i-- ){
while(st.size() > 0 && st.top() <= nums[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(nums[i]) ;
}
reverse(v.begin() , v.end()) ;
return v ;
}Q4) Next Greater to the Left (NGEL)
Approach: Similar to NGER but we iterate from the start instead of the end and we don't reverse the output array
vector<int> NGEL(vector<int>& arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = 0 ; i < n ; i++ ){
while(st.size() > 0 && st.top() <= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(arr[i]) ;
}
return v ;
}Q5) Next smaller element to the right (NSER):
Approach: Similar to NGER Just change the sign while comparing stack top and array element
vector<int> NSER(vector<int> arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = n - 1 ; i >= 0 ; i-- ){
while(st.size() > 0 && st.top() >= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(arr[i]) ;
}
reverse(v.begin() , v.end()) ;
return v ;
}Q6) Next smaller element to the Left (NSEL):
Approach: Similar to NGER. Just traverse from the start , change the sign while comparing stack top and array element and don't reverse the output array
vector<int> NSEL(vector<int>& arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = 0 ; i < n ; i++ ){
while(st.size() > 0 && st.top() >= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(arr[i]) ;
}
return v ;
}Once you know how to find NGER, you get the intuition for NGEL, NSER and NSEL.
Knowing all four techniques NGER, NGEL, NSER and NSEL, you can solve a bunch of problems
Summary:
| Problem | Stack Type | Operator in while loop |
|---|---|---|
| next greater right | decreasing | stackTop <= current |
| previous greater | decreasing | stackTop <= current |
| next smaller | increasing | stackTop >= current |
| previous smaller | increasing | stackTop >= current |
Q7) Temperature Rise ( Try on your own)
Approach: Same as Next Greater to Right just store the index instead of the value
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st ;
vector<int> v ;
int n = temperatures.size() ;
for(int i = n-1; i >= 0; i-- ){
while(st.size() > 0 && temperatures[st.top()] <= temperatures[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(0) ;
}else{
v.push_back(st.top()-i) ;
}
st.push(i) ;
}
reverse(v.begin(), v.end()) ;
return v ;
}Q8) Stock span problem very famous problem
Input: N = 7, price[] = [100 80 60 70 60 75 85]
Output: : 1 1 1 2 1 4 6
Explanation: Traversing the given input span for 100 will be 1, 80 is smaller than 100 so the span is 1, 60 is smaller than 80 so the span is 1, 70 is greater than 60 so the span is 2 and so on. Hence the output will be 1 1 1 2 1 4 6.
Approach: Just recognize which pattern this question out of NGER, NGEL, NSER, and NSEL
It is NGER since we need to find the greater stock price and store the difference in the array.
vector <int> calculateSpan(int arr[], int n){
stack<int> st ;
vector<int> v ;
for( int i = 0 ; i < n ; i++ ){
while(st.size() > 0 && arr[st.top()] <= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(i + 1) ;
}else{
v.push_back(i - st.top()) ;
}
st.push(i) ;
}
return v ;
}
Q9) Maximum Area Histogram
Approach: Again this question is a combination of 2 problems: NSER and NSEL. We need to find consecutive bigger elements so we use the Nearest smaller concept. The only change is that when the stack is empty in NSER we push the last index and in NSEL we push -1 (index before 0)
int largestRectangleArea(vector<int>& heights) {
// Instead of -1 push the last index (n) if stack is empty
vector<int> right = NSER(heights) ;
// Push -1 if stack is empty
vector<int> left = NSEL(heights) ;
int ans = -1 ;
for(int i=0 ;i<heights.size() ;i++){
ans=max(ans,(right[i]-left[i]-1)*heights[i]);
}
return ans ;
}
Full Code:
vector<int> NSER(vector<int> arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = n - 1 ; i >= 0 ; i-- ){
while(st.size() > 0 && arr[st.top()] >= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(n) ;
}else{
v.push_back(st.top()) ;
}
st.push(i) ;
}
reverse(v.begin() , v.end()) ;
return v ;
}
vector<int> NSEL(vector<int> arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = 0 ; i < n ; i++ ){
while(st.size() > 0 && arr[st.top()] >= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(-1) ;
}else{
v.push_back(st.top()) ;
}
st.push(i) ;
}
return v ;
}
int largestRectangleArea(vector<int>& heights) {
vector<int> right = NSER(heights) ;
vector<int> left = NSEL(heights) ;
int ans = -1 ;
for(int i=0 ;i<heights.size() ;i++){
ans=max(ans,(right[i]-left[i]-1)*heights[i]);
}
return ans ;
}Q10) Max Area Rectangle in binary matrix
Approach: Direct Implementation of Max Area in a Histogram(MAH). Apply MAH to every row of the matrix with 1 catch:. If the element is 0 then the whole column becomes if it is 1 then add it to the vector and apply MAH.
Return maximum value amongst all answers.
int maximalRectangle(vector<vector<char>>& nums) {
if(nums.size() == 0){
return 0 ;
}
vector<int> ds ;
for(int j = 0 ; j < nums[0].size() ; j++){
if(nums[0][j] == '1'){
ds.push_back(1) ;
}else{
ds.push_back(0) ;
}
}
int mx = largestRectangleArea(ds) ;
for(int i = 1 ; i< nums.size() ; i++ ){
for(int j = 0 ; j<nums[i].size() ; j++ ){
if(nums[i][j] != '0'){
ds[j]++ ;
}else{
ds[j] = 0 ;
}
}
mx = max(largestRectangleArea(ds) , mx);
}
return mx ;
}Q11. Valid Subarrays
Given array nums of integers, return the number of non-empty continuous subarrays that satisfy the following condition:
The leftmost element of the subarray is not larger than other elements in the subarray.
vector<int> countOfSubArray(vector<int> arr){
stack<int> st ;
vector<int> v ;
int n = arr.size() ;
for( int i = n - 1 ; i >= 0 ; i-- ){
while(st.size() > 0 && arr[st.top()] >= arr[i]){
st.pop() ;
}
if(st.size() == 0){
v.push_back(n-i) ;
}else{
v.push_back(st.top()-i) ;
}
st.push(i) ;
}
reverse(v.begin() , v.end()) ;
return v ;
}Next 3 problems are quite tough and its okay if you don't get their solution yourself
Maintain a monotonic equal or incresing stack
- The method is straightforward. We want the smallest number possible, so we start by removing the most significant digits first. For example, if we have the digits 1-4, then the smallest number would be 1234 and not 2314 or any other combination. To achieve this, we remove any digit that is greater than the following digit. So in the case of 2314, we first remove 3 as it is greater than 1 and then 2 since it is also greater than 1.
- To implement this, we use a stack data structure. Whenever the top digit on the stack is greater than the current digit, we pop it off.
- The conditions in the while loop are crucial to avoid runtime errors. For example, in the case of ["10001", 2], the answer is "0", but if we don't specify the condition !s.empty(), then the while loop will try to pop from an empty stack, causing a runtime error.
string removeKdigits(string num, int k) {
stack<int> st ;
string op = "" ;
for(int i = 0 ; i < num.size() ; i++ ){
while(st.size() > 0 && k > 0 && st.top() > num[i] ){
st.pop() ;
k-- ;
}
st.push(num[i]) ;
}
while(st.size() > 0 && k > 0){
st.pop() ;
k-- ;
}
while(!st.empty()){
op += st.top() ;
st.pop() ;
}
reverse(op.begin() , op.end()) ;
int s = 0;
while (s < (int)op.size()-1 && op[s]=='0') s++;
op.erase(0, s);
return op == "" ? "0" : op ;
}Q13. 132 Pattern
Montonic Strictly Decreasing Stack
bool find132pattern(vector<int>& nums) {
int n = nums.size() ;
stack<pair<int, int>> st ;
int curr_min = nums[0];
for (int i = 1; i < n ; i++) {
while (!st.empty() && nums[i] >= st.top().first){
st.pop();
}
if (!st.empty() && nums[i] > st.top().second){
return true;
}
curr_min = min(nums[i], curr_min);
st.push({nums[i], curr_min});
}
return false;
}Q14. Maximum Subarray Min-Product
Monotonic Increasing Stack
- In order to find the minimum product, we can't simply calculate the minimum from all sub arrays as it will result in a time limit exceeded (TLE) error.
- So, instead, we take each element nums[i] (where 0 <= i < n) as the minimum element and find the minimum product of subarrays with nums[i] as the minimum.
- We first calculate the prefix sum of the given array and then determine the number of largest elements to the left in the "array left" and the number of largest elements to the right in the "array right" with nums[i] as the minimum.
- After finding this information, it becomes straightforward to find the length of the subarray with nums[i] as the minimum. To find the starting index (a), we use the equation a = i - left[i] + 1, and for the ending index (b), we use b = i + right[i] - 1.
- Then, we calculate the result by using the prefix sum and knowing that the minimum element is nums[i].
- Finally, we update the result by finding the maximum of the minimum product.
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
int left[n], right[n];
long long int sum[n];
sum[0] = nums[0];
for(int i=1;i<n;i++){
sum[i] = sum[i-1]+nums[i];
}
stack<pair<int, int> > s1, s2;
for (int i = 0; i < n; ++i) {
int cnt = 1;
while (!s1.empty() && (s1.top().first) > nums[i]) {
cnt += s1.top().second;
s1.pop();
}
s1.push({ nums[i], cnt });
left[i] = cnt;
}
for (int i = n - 1; i >= 0; --i) {
int cnt = 1;
while (!s2.empty() && (s2.top().first) >= nums[i]) {
cnt += s2.top().second;
s2.pop();
}
s2.push({ nums[i], cnt });
right[i] = cnt;
}
long long int res =0;
for(int i=0;i<n;i++){
int a = i-left[i]+1;
int b = i+right[i]-1;
long long int subArraySum;
if(a>0)
subArraySum = sum[b]-sum[a-1];
else
subArraySum = sum[b];
res = max(res, subArraySum*nums[i]);
}
return res%1000000007;
}2. Stack Parenthesis Questions
Q1) Valid Parenthesis
We push the opening bracket in the stack and if we encounter any type of closing bracket then we check if stack top should be equal to that closing bracket else we return false
bool isValid(string s) {
stack<char> st ;
for(int i = 0 ;i < s.size() ; i++ ){
if(s[i] == '(' || s[i] == '[' || s[i] == '{' ){
st.push(s[i]) ;
}else if(s[i] == ')' && (st.empty() || st.top() != '(' )){
return false ;
}else if(s[i] == ']' && (st.empty() || st.top() != '[' )){
return false ;
}else if(s[i] == '}' && (st.empty() || st.top() != '{')){
return false ;
}else{
st.pop() ;
}
}
return st.empty() ;
}Q2. Redundant Parenthesis
If we encounter a closing bracket and immediately on top we find an opening bracket then it is redundant, else we pop all elements until we reach the opening bracket.
bool isRedundantParenthesis(string s){
stack<char> st ;
for(int i=0 ; i < s.size() ; i++ ){
if(s[i] == ')'){
if(st.top() == '('){
return true ;
}else{
while(st.top() != '('){
st.pop() ;
}
st.pop() ;
}
}else{
st.push(s[i]) ;
}
}
return false ;
}Q3. Minimum Add To Make Parentheses Valid
Similar to Q1
int minAddToMakeValid(string s) {
stack<char> st ;
int count = 0 ;
for(int i = 0 ;i < s.size() ; i++ ){
if(s[i] == '(' ){
st.push(s[i]) ;
}
// If the character is closing bracket and either if stack is empty or stack top is not an opening bracket then it is invalid
else if(s[i] == ')' && (st.empty() || st.top() != '(' )){
count++ ;
}else{
st.pop() ;
}
}
// if stack is not empty we add that to the count as well
return count + st.size();
}Q5. Longest Valid Parentheses
Brute Force: Extension of Is Valid Parenthesis Problem.
Basically, check for every substring validity and return the longest substring
int longestValidParentheses(string s) {
int mx = 0 ;
for(int i = 0; i < s.size(); i++){
string temp = "" ;
temp += s[i] ;
for(int j = i + 1; j < s.size(); j++){
temp += s[j] ;
cout<<temp ;
if(isValid(temp)){
int n = temp.size() ;
mx = max(mx, n) ;
}
}
}
return mx ;
}Efficient Approach:
int longestValidParentheses(string s) {
stack<int> st ;
st.push(-1) ;
int mx = 0 ;
for(int i = 0; i < s.size(); i++){
if(s[i] == '('){
st.push(i) ;
}else{
st.pop() ;
if(st.empty()){
st.push(i) ;
}else{
mx = max(mx, i - st.top()) ;
}
}
}
return mx ;
}Q6. Reverse each word
string reverseWords(string s) {
stack<string>st;
for(int i =0;i<s.length();i++){
string word="";
if(s[i]==' ')continue;
while(s[i]!=' ' and i<s.length()){
word+=s[i];
i++;
}
st.push(word);
}
string ans="";
while(!st.empty()){
ans+=st.top();
st.pop();
if(!st.empty())ans+=" ";
}
return ans;
}Pattern 3: Implementation-type Problems
- While pushing
if x < minEle : push 2*x-minEle and put the provided x in st - Similarly while popping
if s.top() < minEle(indicates the flag): Restore the mn before popping: minEle = 2* minEle -st.top()
Q1. Min Stack
class MinStack {
public:
stack<long long int> st ;
long long int minEle;
MinStack() {
minEle = INT_MIN;
}
void push(int val) {
if(st.empty()){
minEle = val;
st.push(val);
}else{
if(val < minEle){
st.push((1ll * 2*val) - minEle);
minEle = val;
}else{
st.push(val);
}
}
}
void pop() {
if(st.top() < minEle){
minEle = 2*minEle - st.top();
st.pop();
}else{
st.pop();
}
}
int top(){
if(st.top() < minEle){
return minEle;
}
return st.top();
}
int getMin() {
return minEle;
}
};- We will consider a frequency map that will count the occurences of each element.
- We will also consider a map group_stack which will group the elements with the same frequecy. Example if two elements have same count then we will add them in stack with the recent element at the top.
- When we will push the elements
*We will increment its frequency
*Update the maximum occurence element
*group the element with its frequency - When we will pop the element from stack
*We will take out the max_frequency element.
*Remove it from group_stack
*Decrement its freuency
*Return it
class FreqStack {
public:
//This will store the count of each element
unordered_map<int,int> frequency;
//This maps the elements which have same count
//But the element that come last will come first of same count
unordered_map<int,stack<int>> group_stack;
//Maximum frequency possible
int max_frequency=0;
FreqStack() {
}
//Push elements in the stack
void push(int val) {
//Increment the count
frequency[val]++;
//Check is this element occurs maximum time
max_frequency=max(max_frequency,frequency[val]);
//Map the element with its count
group_stack[frequency[val]].push(val);
}
int pop() {
//Find the max occurence element
int top_max_frequency=group_stack[max_frequency].top();
//Remove it from stack
group_stack[max_frequency].pop();
//Decrement its count
frequency[top_max_frequency]--;
//If there is no element of maximum frquency the decrement max_frequency
if(group_stack[max_frequency].size()==0)
max_frequency--;
return top_max_frequency;
}
};Pattern 4: Advanced Stack Problems
- Sort the intervals .
- While traversing the intervals vector we will come accross two coditions
- First condition : if there is a overlapping between the intervals then just take out the max element from the ending point and thus we merged them
eg:- [1,4],[2,8] =Mergerd intervals will be> [1,8] - Second condition : if there is no overlapping then simply push those interval to our resultant vector .
- First condition : if there is a overlapping between the intervals then just take out the max element from the ending point and thus we merged them
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(!intervals.size()) return {};
sort(intervals.begin(),intervals.end());
vector<vector<int>>v;
stack<vector<int>> st ;
st.push(intervals[0]) ;
for(int i = 1 ; i<intervals.size() ; i++){
if(intervals[i][0] > st.top()[1]){
st.push(intervals[i]) ;
}else{
st.top()[1] = max(intervals[i][1], st.top()[1]) ;
}
}
while(!st.empty()){
v.push_back(st.top()) ;
st.pop() ;
}
reverse(v.begin() , v.end()) ;
return v ;
}vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(newInterval) ;
// Function of Q1 Merge Intervals
return merge(intervals) ;
}- Whenever we encounter a positive value, we will simply push it to the stack.
- The moment we encounter a negative value, we know some or all or zero positive values will be knocked out of the stack. The negative value may itself be knocked out or it may enter the stack.
vector<int> asteroidCollision(vector<int>& ast) {
int n = ast.size();
stack<int> st;
for(int i = 0; i < n; i++) {
if(ast[i] > 0 || st.empty()) {
st.push(ast[i]);
}else {
while(!st.empty() and st.top() > 0 and st.top() < abs(ast[i]) ) {
st.pop();
}
if(!st.empty() and st.top() == abs(ast[i])) {
st.pop();
}else if(st.empty() || st.top() < 0) {
st.push(ast[i]);
}
}
}
// finally we are returning the elements which remains in the stack.
// we have to return them in reverse order.
vector<int> res(st.size());
for(int i = (int)st.size() - 1; i >= 0; i--) {
res[i] = st.top();
st.pop();
}
return res;
}Q4. Celebrity Problem
Very interesting problem since the date is of O(n^2) and we need Time Complexity of O(n)
We initially push all the elements in the stack then compare the celebrity among them.
Lats element in the stack is the potential celebrity
Then we traverse the pot row and column to actual confirm whether it is actually a celebrity or not.
int celebrity(vector<vector<int> >& arr, int n){
stack<int> st ;
for(int i = 0 ; i < n ; i++ ){
st.push(i) ;
}
while(st.size() >= 2){
int top1 = st.top() ;
st.pop() ;
int top2 = st.top() ;
st.pop() ;
if(arr[top1][top2] == 1){
st.push(top2) ;
}else{
st.push(top1) ;
}
}
int pot = st.top() ;
for(int i = 0 ; i < arr.size() ; i++ ){
if(i != pot){
if(arr[pot][i] == 1 || arr[i][pot] == 0){
return -1 ;
}
}
}
return pot ;
}Q5. Construct Smallest Number From DI String
- If we have encountered I or we are at the last character of input string, then pop from the stack and add it to the end of the output string until the stack gets empty.
- If we have encountered D, then we want the numbers in decreasing order. so we just push (i+1) to our stack.
string printMinNumberForPattern(string s){
stack<int> st;
string ans = "";
int n = 1 ;
for(int i=0; i<s.size();i++){
st.push(n);
n++ ;
if(s[i] == 'I'){
while(st.size()!=0){
ans += to_string(st.top());
st.pop();
}
}
}
st.push(n);
while(st.size()!=0){
ans += to_string(st.top());
st.pop();
}
return ans;
}Q6. Evaluate Reverse Polish Notation
int evalRPN(vector<string>& tokens) {
stack<string> st ;
for(auto it: tokens){
if(it == "+"){
string tp1 = st.top() ;
st.pop() ;
string tp2 = st.top() ;
st.pop() ;
st.push(to_string(stol(tp2) + stol(tp1))) ;
}else if(it == "-"){
string tp1 = st.top() ;
st.pop() ;
string tp2 = st.top() ;
st.pop() ;
st.push(to_string(stol(tp2) - stol(tp1))) ;
}else if(it == "*"){
string tp1 = st.top() ;
st.pop() ;
string tp2 = st.top() ;
st.pop() ;
st.push(to_string(stol(tp2) * stol(tp1))) ;
}else if(it == "/"){
string tp1 = st.top() ;
st.pop() ;
string tp2 = st.top() ;
st.pop() ;
st.push(to_string(stol(tp2) / stol(tp1))) ;
}else{
st.push(it) ;
}
}
return stoi(st.top()) ;
}- By looking at examples we can see that the above simplification process just behaves like a stack.
- Whenever we encounter any file’s name, we simply push it into the stack.
- When we come across ” . ” we do nothing.
- When we find “..” in our path, we simply pop the topmost element as we have to jump back to parent’s directory.
- When we see multiple “////” we just ignore them as they are equivalent to one single “/”.
- After iterating through the whole string the elements remaining in the stack is our simplified absolute path.
string simplifyPath(string path) {
stack<string> st;
string res;
for(int i = 0; i<path.size(); ++i)
{
if(path[i] == '/')
continue;
string temp;
// iterate till we doesn't traverse the whole string and doesn't encounter the last /
while(i < path.size() && path[i] != '/')
{
// add path to temp string
temp += path[i];
++i;
}
if(temp == ".")
continue;
// pop the top element from stack if exists
else if(temp == "..")
{
if(!st.empty())
st.pop();
}
else
// push the directory file name to stack
st.push(temp);
}
// adding all the stack elements to res
while(!st.empty())
{
res = "/" + st.top() + res;
st.pop();
}
// if no directory or file is present
if(res.size() == 0)
return "/";
return res;
}