sol_061.md

Implement Min Stack - Practice - Work@Tech

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 non-empty stack.

Example:1

Input: 
1
7
push 1
push 2
push -1
getMin
pop
top
getMin

Output: 
-1 2 1

Solution 1

Time - O(1)
Space - O(2n)

// Implement the below class
class MinStack {
	stack<int> s1, s2;	
	public:
    void push(int x) {
		if (s1.empty()){
			s2.push(x);
		}
		else if(x <= s2.top()){
			s2.push(x);
		}
		s1.push(x);
    }
    void pop() {
	    if (!s1.empty()){
			if (s1.top() == s2.top()){
				s2.pop();
			}
			s1.pop();
		}
    }
    int top() {
		if (!s1.empty())
			return s1.top();
		return -1;	    
    }
    int getMin() {
		if (!s1.empty())
			return s2.top();
		return -1;	    
    }
};

/*
	// MinStack class and its object will be used as given below:
	MinStack *minStack = new MinStack();
	minStack->push(42);
	int top = minStack->top();
	int min = minStack->getMin();
	minStack->pop();
*/