Min Stack

Question

Design a special stack that supports all the stack operations such as push(), pop(), top() along with an additional operation getMin() that returns the minimum element in the stack. All of these operations should take O(1) time to complete.

 

Example:  Consider the following special Stack: 16  --> TOP 17 18 19 When getMin() is called, it should return 16, the minimum element in the current stack.  If we do pop two times on stack, the stack becomes 18  --> TOP 19 When getMin() is called, it should return 19, the minimum in the current stack.

 

It should be done in O(1) time.

Input

 

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-3],[0],[-5],[],[],[],[]]

 

Output

 

[null,null,null,null,-3,null,0,-2]

 

Explanation

 

MinStack minStack = new MinStack();

minStack.push(-3);

minStack.push(0);

minStack.push(-5);

minStack.getMin();     // return -5

minStack.pop();

minStack.top();         // return 0

minStack.getMin();  // return -3

 

Implement the MinStack class:

C++ code

class MinStack { public:     MinStack() {              }     void push(int val) {              }      void pop() {              }     int top() {              }     int getMin() {             } };

 

• MinStack() initializes the stack object.
• void push(int val) pushes the element val into the stack.
• void pop() removes the topmost element of the stack.
• int top() returns the topmost element of the stack.
• int getMin() returns the minimum element in the stack.

 

---

 

Recommended: Please try to solve it yourself first before moving on to 

the solution. 

 

---

 

Solution

Here, we are going to discuss multiple approaches. Starting from using extra space, we will improve the space complexity and discuss some better solutions. Continue reading till the end of the blog. 

As a stack generally do the push(), pop(), and top() operations in O(1) time, we have to make getMin() function in O(1) time complexity.

Approach 1: Using Stack and Multiset Approach. 

 

The idea behind this logic is to have one stack to do stack operations and one multiset to get min element of the stack.

 

Multisets are similar to set, except that multiple elements can have the same values. A set stores the values in increasing order, so getting a minimum element in a set is O(1) time, i.e., *s.begin().

 

push(int val)  Operation

• We will push elements both in the stack as well as multiset during push operations.

 

pop() Operation

• We will pop the element from the stack and delete that element from the multiset.

 

top() Operation

• Return the topmost element of the stack.

 

getMin() Operation

• Return 1st element of the multiset. It will be the smallest element of the stack.

 

C++ code:

class MinStack {       private:              stack<int> st; multiset<int> ms;           public:  //insert elements on both set and stack             void push(int val) { st.push(val);  ms.insert(val); } //poping elements on both set and stack             void pop() { int top = st.top(); st.pop(); ms.erase(ms.find(top));  } //return stack top             int top() {                      return st.top(); } // return set first element              int getMin() {  return *ms.begin(); } };

 

Here time complexity is O(NlogN). As set/multiset insertion takes O(logN) time.

Approach 2: Using Two Stack Approach

• The idea is to keep stack1 to store actual stack elements and stack2 to store the minimum elements.

 

• Push(int val) operation:
  • Push element in stack1.
  • We will push elements in stack2 only if stack2 is empty or the val element is smaller than or equal to the topmost element of stack2. With this, the top of stack2 will always be minimum.

 

• Pop() Operation
  • Pop the element from stack1.
  • We will pop from stack2 only if top of stack1 and stack2 both are equal.

 

• top() Operation
  • Return the topmost element of stack1.

 

• getMin() Operation
  • Return the topmost element of stack2.

C++ code:

class MinStack {                private:               stack<int> stack1, stack2; public: void push(int val) { // push val in stack1, simple stack operation                     stack1.push(val);  if(stack2.empty() || val <= stack2.top()){                   // push in stack2 only if val < current minimum                           stack2.push(val); } } void pop() { if(stack2.top() == stack1.top())                                stack2.pop();                     stack1.pop(); } int top() {//return top element of the stack1 return stack1.top(); } int getMin() { //return top element of stack2 return stack2.top(); } };

Approach 3: Optimal Solution, using one stack only.

 

The idea is to keep one stack to do push(), pop(), top() operations, and a variable minElement that stores the current minimum element in the stack.

Now the interesting part is when the minimum element is removed in pop() operation. To handle this, we push minElement into the stack when the new value is smaller than minEement. Because of this, the previous minimum element can be retrieved as its value is stored in the stack. Below are the detailed steps and an explanation of working.

 

push(int val) Operation

• If ‘val’ is less than or equal to the minElement, push the minElement into the stack and then insert val into the stack. Also update minElement to ‘val’.

 

pop() Operation

• If minElement is equal to the topmost element of the stack.
  • Remove the top element from the stack.
  • The updated topmost element is the new minimum element, so update minElement as stack.top() and then pop it out from the stack.

 

• Else if minElement is not equal to the topmost element of the stack
  • pop the element from the stack.

 

top() Operation

• Return the topmost element of the stack.

 

getMin() Operation

• Return the variable value minElement. This will take O(1) time. 

 

C++ code

class MinStack { private:               stack<int> st;  int minElement = INT_MAX;//initalize with max value                 public: void push(int val) { if(minElement >= val){                           st.push(minElement); minElement = val; } st.push(val); } void pop() { if(minElement == st.top()){                           st.pop(); minElement = st.top();                           st.pop(); } else{                           st.pop();                    } } int top() { return st.top(); } int getMin() { return minElement; } };

 

Must Read Stack Operations