It is required to create a method getMinimum() which will give us the minimum in the current stack in O(1) time complexity. we will be using another stack for this to store the minimum at any particular point in time.
We will take an auxiliary stack that maintains the minimum of all values in the stack. Also, assume that each element of the stack is less than it's below elements. For simplicity let us call the auxiliary stack as min stack.
When we pop the main stack, pop the min stack too. When we push the main stack, push either the new element or the current minimum, whichever is lower. At any point, if we want to get the minimum then wee justs need to return the top element fro the min stack. Let us take some example and trace out.
Java solution for the given problem is as below:
package askgif.linkedlist;
import java.util.Stack;
class MyStack{
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public MyStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int data) {
stack.push(data);
if(minStack.isEmpty())
minStack.push(data);
else if(minStack.peek() > data)
minStack.push(data);
}
public int pop() {
if(stack.isEmpty())
return 0;
int data = stack.pop();
if(minStack.peek() == data)
minStack.pop();
return data;
}
public void printMinimum() {
System.out.println(minStack.peek());
}
}
public class Stacks {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(10);
stack.push(5);
stack.printMinimum();
stack.push(15);
stack.push(12);
stack.printMinimum();
stack.pop();
stack.printMinimum();
stack.pop();
stack.printMinimum();
stack.pop();
stack.printMinimum();
}
}
output:
5
5
5
5
10
Time Complexity: O(1)
Space Complexity: O(n) for an extra stack.
