Max stack  

Difficulty Level Easy
Frequently asked in Apple lyft Uber
Design Stack

Problem Statement  

The problem “Max stack” states to design a special stack which can perform these operations :

  1. push(x): push one element into the stack.
  2. top(): returns the element that is at the top of the stack.
  3. pop(): remove the element from the stack which is at the top.
  4. peekmax(): returns the maximum element of the stack.
  5. popmax(): removing the maximum element from the stack and return it.

If the stack contains multiple Maximum elements then for popmax() remove only one element that is the topmost.

For the last four operations, this is for sure that the stack is not empty otherwise these operations won’t be called.

Example  

push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

Explanation

Please click Like if you loved this article?

Max StackPin

Approach  

The approach is very simple. Here we will maintain a max stack that will keep track of maximum element in the stack so far. Since starting three operations are supported by normal stack so we have to program especially for the last two operations.

peekmax()

Suppose we have stack [5,2,3,6,8] so we will maintain another stack. let name it as the max stack which will store the maximum till that element. So for the given stack, our max stack will be [5,5,5,6,8]. In this way, we can find the maximum element in O(1) time complexity.

See also
Remove duplicates from sorted array

popmax()

Using peekmax() we can easily find the maximum element in the stack. So we will pop elements from the stack and push it into a buffer stack. We will repeat this until we found the maximum element.

Then we will pop the maximum element from the stack. After that we will transfer all the elements in the buffer stack to our original stack.

Code  

C++ code for Max Stack

class MaxStack {
    public MaxStack() {
         stack<int> tmpStack, maxStack;
    }
    public void push(int x) {
        int max = maxStack.empty() ? x : maxStack.top();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        int tmp=tmpStack.top();
        tmpStack.pop();
        maxStack.pop();
        return tmp;
    }
    public int top() {
        return tmpStack.top();
    }
    public int peekMax() {
        return maxStack.top();
    }
    public int popMax() {
        int mx = peekMax();
        stack<int> buffer;
        while (tmpStack.top() != mx){
            buffer.push(tmpStack.top());
            tmpStack.pop();
        }
        while (!buffer.empty()){
            tmpStack.push(buffer.top());
            buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

Java code for Max Stack

class MaxStack {
    Stack<Integer> tmpStack;
    Stack<Integer> maxStack;
    public MaxStack() {
        tmpStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        maxStack.pop();
        return tmpStack.pop();
    }
    public int top() {
        return tmpstack.peek();
    }
    public int peekMax() {
        return maxStack.peek();
    }
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<Integer>();
        while(tmpStack.top() != mx){
        	buffer.push(tmpStack.top());
        	tmpStack.pop();
        }
        while (!buffer.isEmpty()){
        	tmpStack.push(buffer.top());
        	buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

Complexity Analysis  

Time complexity

  1. push(x): O(1) we can push elements into the stack in a single step.
  2. pop(): O(1) we can pop an element from the stack in a single step.
  3. top(): O(1) we can return the top element of the stack in a single step.
  4. peekmax(): O(1) we can find maximum element in the stack in a single step.
  5. popmax(): O(n) in the worst case the maximum element may be at the bottom of the stack.
See also
Largest Substring Between Two Equal Characters Leetcode Solution

Space complexity

O(n) in the worst case all elements are present in the stack at the same time.

Please click Like if you loved this article?