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 BigO 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
 return top value of buff
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 upvote. Happy Coding :)