Implement Min Stack Editorial

Practice Problem Link: Min Stack

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement a stack that supports the following operations in O(1) time complexity:

• push(x) : Push the element x onto the stack.
• pop() : Removes the element at the top of the stack.
• top() : Get the topmost element of the stack.
• getMin() : Get the minimum element in the stack.

Assume that pop, top and getMin will only be called on a non-empty stack.

Naive Approach:

The push, pop, and top functions can be implemented using a simple stack. For the getMin function, we can use a vector to store the other operations and then find the minimum element in O(n) time.

Analysis:

• Time Complexity: push() -> O(1), pop() -> O(1), top() -> O(1), getMin() ->O(n)
• Space Complexity: push() -> O(1), pop() -> O(1), top() -> O(1), getMin() ->O(n)

Optimal Approach: 

In the optimal approach, the push, pop, and top operations stay the same as in the naive approach. For the getMin function, we use 2 stacks that represent the pair of (top element, current minimum in the stack). Then, we can simulate the getMin function in O(1) time too.

Analysis:

• Time Complexity: push() -> O(1), pop() -> O(1), top() -> O(1), getMin() ->O(1)
• Space Complexity: push() -> O(1), pop() -> O(1), top() -> O(1), getMin() ->O(1)

Implementation:

C++

class MinStack {
public:
	stack<int> stack1, stack2;
    void push(int x) {
		stack1.push(x);
	    if (stack2.empty() || x <= getMin()) {
            stack2.push(x);
        }
    }
    void pop() {
	    if (stack1.top() == getMin()) {
            stack2.pop();
        }
	    stack1.pop();
    }
    int top() {
	    return stack1.top();
    }
    int getMin() {
	    return stack2.top();
    }
};

Java

class MinStack {
	Stack<Integer> stack1 = new Stack<Integer>();
	Stack<Integer> stack2 = new Stack<Integer>();
    void push(int x) {
		stack1.push(x);
	    if (stack2.isEmpty() || x <= getMin()) {
            stack2.push(x);
        }
    }
    void pop() {
	    if (stack1.peek() == getMin()) {
            stack2.pop();
        }
	    stack1.pop();
    }
    int top() {
	    return stack1.peek();
    }
    int getMin() {
	    return stack2.peek();
    }
}