Home » Technical Interview Questions » Stack Interview Questions » Tracking current Maximum Element in a Stack

Tracking current Maximum Element in a Stack


Reading Time - 4 mins

Problem Statement

“Tracking current Maximum Element in a Stack” states that you are given a stack data structure. Create a function to keep the track of the maximum value in the stack till the current index.

Tracking current Maximum Element in a Stack

Example

4 19 7 14 20
4 19 19 19 20

Explanation: The maximum values until the current indices are to be printed and they are shown in the above image. As we encounter a number which is greater than the current maximum. The value of current maximum changes.

40 19 7 14 20 5
40 40 40 40 40 40

Naive Method

Algorithm

1. Initialize a stack data structure of integer type.
2. Create an integer variable max and store the element at the top of the stack in it.
3. Whenever we need to find the maximum element, we create a temporary stack to store the elements of main stack.
4. Remove each element from mainStack and store in tmpStack while maintaining the maximum.
4. Print the max.

In naive approach, we keep an extra temporary stack which is used to find the maximum. Every time whenever we need to find the maximum, we traverse all the elements of mainStack. So to traverse the elements we need to pop them out of the main stack and push them into the temporary stack.  So that after traversing all the elements we can push them back into the main stack. Thus whenever we need to the maximum until now, the operation costs a linear time complexity of O(N). Thus if we find the maximum until every element, the total time complexity will be O(N^2).

READ  Identify and Mark Unmatched Parenthesis in an Expression

Code

C++ Program for Tracking current Maximum Element in a Stack

#include <bits/stdc++.h>
using namespace std;

class StackWithMax{
    stack<int> mainStack;

public:
    void push(int x){
        mainStack.push(x);
    }

    int getMax(){
        stack<int> tmpStack;
        int mx = INT_MIN;
        while(!mainStack.empty()){
            tmpStack.push(mainStack.top());
            mainStack.pop();
            mx = max(tmpStack.top(), mx);
        }
        while(!tmpStack.empty()){
            mainStack.push(tmpStack.top());
            tmpStack.pop();
        }
        return mx;
    }

    int pop(){
        mainStack.pop();
    }
};

int main(){
    StackWithMax s;

    s.push(20);
    s.push(14);
    s.push(7);
    s.push(19);
    s.push(4);
    cout<<s.getMax();

    return 0;
}
20

Java Program for Tracking current Maximum Element in a Stack

import java.util.*; 

class TrackMax{ 
  
    static class StackWithMax{  
        static Stack<Integer> mainStack = new Stack<Integer> ();  
        
        static void push(int x){  
                mainStack.push(x);
        }  
          
        static void getMax(){  
            int max = mainStack.peek();
            while(!mainStack.isEmpty()){
                
                if(max<mainStack.peek()){
                    max = mainStack.peek();
                }
                
                System.out.print(max+" ");
                pop();
            } 
        }  
      
        static void pop(){  
            mainStack.pop();  
        }  
    
    };
      
    public static void main(String[] args){  
        StackWithMax s = new StackWithMax();
        
        s.push(20);  
        s.push(14);  
        s.push(7);  
        s.push(19);  
        s.push(4);  
        s.getMax(); 
    } 
}
20

Complexity Analysis

Time Complexity

O(N), because we traverse all the elements inside the stack per getmax() operation.

Space Complexity

O(N), because we are using a temporary stack to store the elements of the main stack.

Efficient Method

Algorithm

1. Initialize a stack data structure of integer type.
2. Create a class and create two stacks main and temporary of integer type in it.
3. After that, create the function push which accepts an integer variable as it's a parameter. Push/insert the integer variable in the main stack.
4. Check if the size of the main stack is equal to 1, push/insert the integer variable in the temporary stack, and return.
5. If the integer variable is greater than the element at the top of the temporary stack, push/insert the integer variable in the temporary stack.
6. Else push/insert the element at the top of the temporary stack in the temporary stack itself.
7. Similarly, create the function to get the maximum element and return the element at the top of the temporary stack.
8. Also, create the function pop. Pop / remove the element at the top of the temporary stack and the main stack.

Code

C++ Program for Tracking current Maximum Element in a Stack

#include <bits/stdc++.h> 
using namespace std; 
  
class StackWithMax{ 

    stack<int> mainStack; 
  
    stack<int> trackStack; 
  
public: 
    void push(int x){ 
        mainStack.push(x); 
        
        if(mainStack.size() == 1){ 
            trackStack.push(x); 
            return; 
        } 
  
        if(x > trackStack.top()){ 
            trackStack.push(x); 
        }
        
        else{
            trackStack.push(trackStack.top()); 
        }
    } 
  
    int getMax(){ 
        return trackStack.top(); 
    } 
  
    int pop(){ 
        mainStack.pop(); 
        trackStack.pop(); 
    } 
}; 
  
int main(){ 
    StackWithMax s; 
    
    s.push(4); 
    cout<<s.getMax()<<" ";
    s.push(19);
    cout<<s.getMax()<<" ";
    s.push(7); 
    cout<<s.getMax()<<" ";
    s.push(14); 
    cout<<s.getMax()<<" ";
    s.push(20); 
    cout<<s.getMax(); 
    
    return 0; 
}
4 19 19 19 20

Java Program for Tracking current Maximum Element in a Stack

import java.util.*; 

class TrackMax{ 
  
    static class StackWithMax{  
        static Stack<Integer> mainStack = new Stack<Integer> ();  
      
        static Stack<Integer> trackStack = new Stack<Integer> ();  
      
    static void push(int x){  
            mainStack.push(x);
            
            if(mainStack.size() == 1){  
                trackStack.push(x);  
                return;  
            }  
      
            if(x > trackStack.peek()){  
                trackStack.push(x);  
            }
            
            else{
                trackStack.push(trackStack.peek());  
            }
        }  
      
        static int getMax(){  
            return trackStack.peek();  
        }  
      
        static void pop(){  
            mainStack.pop();  
            trackStack.pop();  
        }  
    };  
      
    public static void main(String[] args){  
        StackWithMax s = new StackWithMax();
        
        s.push(4);  
        System.out.print(s.getMax()+" ");  
        s.push(19);  
        System.out.print(s.getMax()+" ");  
        s.push(7);  
        System.out.print(s.getMax()+" "); 
        s.push(14);  
        System.out.print(s.getMax()+" ");  
        s.push(20);  
        System.out.print(s.getMax()); 
    } 
}
4 19 19 19 20

Complexity Analysis

Time Complexity

O(1), because we are finding the maximum in constant time.

READ  Reverse a Number Using Stack

Space Complexity

O(N), here instead of finding the maximum element we are storing the maximum element at the time of input which gave us linear space complexity.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions