Problem
Find the minimum value in a stack with O(1) time complexity.
Solution
Iterate through the stack elements for the minimum value takes O(N), won't satisfy the criteria. The only way to make it work is to have the minimum value stored so that we can return it in instant time. How to store the minimum value? A variable won't work. Once we pop out the min value, we won't be able to know what is the next minimum value in the stack. We need to store a sequence of minimum values in a stack or queue. We are not clear what should be stored, so let's play with an example.
push 3, 5, 7, 2, 5
when push 3, we record 3 as min.
when push 5, 7, we don't care, they are larger anyway.
when push 2, we got a new min, so we store 2 above 3, that tells us we need a stack as the storage.
when push 5, we don't care.
Now we got two stacks:
value stack: 5, 2, 7, 5, 3
min stack: 2, 3
Now let's pop the value stack.
pop 5, we don't care, it didn't change min value.
pop 2, our min value changes, so we also pop 2 from the min stack.
pop 7, 5 we don't care.
pop 3, the min value changes, so we pop 3 from the min stack.
Coding the above is straight forward.
//[5, 3, 3, 7, 2, 8]
//3 3 5
//3 3 5
import java.util.*;
class FastMinStack {
private Stack<Integer> values = new Stack<>();
private Stack<Integer> mins = new Stack<>();
public int getMin() {
if(mins.isEmpty()) throw new RuntimeException("stack is empty");
return mins.peek();
}
public void pop() {
int val = values.pop();
if(val == mins.peek()) mins.pop();
return val;
}
public int push(int val) {
values.push(val);
if(mins.isEmpty() || val <= mins.peek())
mins.push(val);
}
public static void main(String[] args) {
FastMinStack fms = new FastMinStack();
fms.push(5);
fms.push(3);
fms.push(3);
fms.push(7);
fms.push(2);
fms.push(8);
System.out.println(fms.getMin());//2
fms.pop();
System.out.println(fms.getMin());//2
fms.pop();
System.out.println(fms.getMin());//3
fms.pop();
fms.pop();
System.out.println(fms.getMin());//3
fms.pop();
System.out.println(fms.getMin());//5
}
}
//3 3 5
//3 3 5
import java.util.*;
class FastMinStack {
private Stack<Integer> values = new Stack<>();
private Stack<Integer> mins = new Stack<>();
public int getMin() {
if(mins.isEmpty()) throw new RuntimeException("stack is empty");
return mins.peek();
}
public void pop() {
int val = values.pop();
if(val == mins.peek()) mins.pop();
return val;
}
public int push(int val) {
values.push(val);
if(mins.isEmpty() || val <= mins.peek())
mins.push(val);
}
public static void main(String[] args) {
FastMinStack fms = new FastMinStack();
fms.push(5);
fms.push(3);
fms.push(3);
fms.push(7);
fms.push(2);
fms.push(8);
System.out.println(fms.getMin());//2
fms.pop();
System.out.println(fms.getMin());//2
fms.pop();
System.out.println(fms.getMin());//3
fms.pop();
fms.pop();
System.out.println(fms.getMin());//3
fms.pop();
System.out.println(fms.getMin());//5
}
}
The time complexity is O(1) for getMin, the space cost is O(N) in worst case, where the stack is 5 4 3 2 1, we have to store all of them for min values.
