# Solution by rohitnandi12

• Primary Thoughts

Stack is a LIFO (Last in First Out) abstract data type with operations such as push and pop and is a linear data structure.

The Questions demands to get the minimum at any particular instance, it means there will be one or more operations carried on the stack and the updated minimum element has to be returned when the getMin function is called.

Questions To The Interviewer

Many situations are not mentioned in question. Possible questions you can ask to the interviewer are.

• Output when pop is performed on a empty stack
• Output when top is performed on a empty stack
• Output when getMin is performed on a empty stack

In this questions it has been assumed that there wont be any situation when the operations are been made on the empty stack. (This i can to know after experimenting with different test cases)

#### Approach #1 [ Time Limit Exceeded ]

Intuition

Use a stack to hold the new elements. When getMin is called traverse the stack and return the minimum element at that instance.

Java Solution

``````class MinStack {

/** initialize your data structure here. */
Stack<Integer> buff = null;
public MinStack() {
buff = new Stack<>();
}

public void push(int x) {
buff.push(x);
}

public void pop() {
buff.pop();
}

public int top() {
return buff.peek();
}

public int getMin() {
Stack<Integer> temp = new Stack<>();
int currentMin = Integer.MAX_VALUE;

while(!buff.isEmpty()){
if(currentMin>buff.peek())
currentMin = buff.peek();
temp.push(buff.pop());
}
while(!temp.isEmpty()){
buff.push(temp.pop());
}
return currentMin;
}
}

``````

Complexity Analysis

Time complexity :

push : \$\$O(1)\$\$.
pop : \$\$O(1)\$\$.
top : \$\$O(1)\$\$.
getMin : \$\$O(n)\$\$. Though getMin has Big-O of O(n), but you can see from code that elements are traversed twice when getMin is called.

Space complexity : \$\$O(n))\$\$.

#### Approach #2 Using Auxiliary Stack [Accepted]

Intuition

A auxiliary stack, say minSt, can be used which is going to store the minimum at any instance when an element is pushed. At any instance the top element of minSt is going to hold the most updated minimum element. Trick is to on call of pop check if the pop element is the minimum element then pop and element from minSt too.

Java

``````class MinStack {
/** initialize your data structure here. */
Stack<Integer> st = null;
Stack<Integer> minSt = null;
public MinStack() {
st = new Stack<>();
minSt = new Stack<>();
}

public void push(int x) {
st.push(x);
if(minSt.isEmpty()){
minSt.push(x);
}else if(x<=minSt.peek()){
minSt.push(x);
}
}

public void pop() {
if(st.peek().equals(minSt.peek())){
minSt.pop();
}
st.pop();
}

public int top() {
return st.peek();
}

public int getMin() {
return minSt.peek();
}
}

``````

Complexity Analysis

• Time complexity : \$\$O(1)\$\$

• Space complexity : \$\$O(2n)\$\$ for the minSt and buff

#### Approach #3 Without Auxilliary Stack [Accepted]

** Intuition**

We can avoid minSt and store the minimum element in buff itself.

** Algorithm **

constructor

• initialize variable currentMin
• initialize stack buff

push

• push the old minimum value when the current minimum value changes after pushing the new value x
• push the new value

pop

• if pop operation could result in the changing of the current minimum value,
pop twice and change the current minimum value to the last minimum value.

top

getMin

• return currentMin

Java

``````class MinStack {
int currentMin = Integer.MAX_VALUE;
Stack<Integer> buff = new Stack<Integer>();

public void push(int x) {
if(x <= currentMin){
buff.push(currentMin);
currentMin=x;
}
buff.push(x);
}

public void pop() {
if(currentMin == buff.pop()) currentMin=buff.pop();
}

public int top() {
return buff.peek();
}

public int getMin() {
return currentMin;
}
}

``````

Complexity Analysis

• Time complexity : \$\$O(1)\$\$

• Space complexity : \$\$O(n)\$\$ for the buff

Thank You for your up-vote. Happy Coding :-)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.