Max stack

Difficulty Level Easy
Frequently asked in Apple lyft Uber
Design StackViews 3517

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

Max Stack

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.

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.

Space complexity

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

Translate »