I’ve just found that leetcode added new one task and decided solve it 🙂. SO, new task is Min Stack.
Task description:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
As you can see we need to implement Data Structure with some rule. Rule is method getMin should work in O(1) time complexity. OK, let’s go…
We can read here how stack should work . It’s very easy as it LIFO data structure.It means last element always will be on top of the our stack. Good but how to find min ? Yes, we can but it will be not constant time …
First idea I had was related to additional internal stack which contains just min values. What does that mean ? Please take a look to the next code fragment :
public class MinStack {
private Stack<Integer> internal = new Stack<Integer>();
private Stack<Integer> min = new Stack<Integer>();
int minVal = Integer.MAX_VALUE;
public void push(int x) {
internal.push(x);
if (minVal > x) {
minVal = x;
min.push(x);
} else {
min.push(minVal);
}
}
public void pop() {
internal.pop();
minVal = min.pop();
}
public int top() {
return internal.peek();
}
public int getMin() {
return minVal;
}
}
You can see that we have two internal stacks one of them contains real data for LIFO functionality other one
private Stack<Integer> min = new Stack<Integer>();
just min values. If you deeply look to method push you will see that we are pushing input val to min stack if that val < minVal in other cases we are pushing minVal.
It means if we push
-10 11 -7 -20 8
Min stack will contain
-10 -10 -10 -20 -20
during pop method we will delete top element from both stacks and all will be good.
But … leetcode told me – memory limit …
I’ve decided that leetcode wants loop implementation 🙂 and developed it :
class MinStack {
private Stack<Integer> internal = new Stack<Integer>();
int minVal = Integer.MAX_VALUE;
public void push(int x) {
internal.push(x);
if (minVal > x) {
minVal = x;
}
}
public void pop() {
Integer x = internal.pop();
if (x == minVal) {
minVal = findMin(internal);
}
}
private int findMin(Stack<Integer> internal) {
int result = Integer.MAX_VALUE;
for (Integer x : internal) {
if (x <= result) {
result = x;
}
}
return result;
}
public int top() {
return internal.peek();
}
public int getMin() {
return minVal;
}
}
In this solution main functionality is placing in pop method. Main idea – if we deleted element from top, check if that element minVal, if yes, try to find new one minVal. Yes, time complexity for method pop will be O(n) but for getMin O(1),and … leetcode accepted this solution 🙂. But I did not satisfied with that solution and decided to look into leetcode solution (leetcode has new functionality after your solution is accepted you can see “real” solution). So, the general idea of leetcode’s solution is the same like first my (based on 2 stacks) but with some improvements
class MinStack {
private Stack stack = new Stack<>();
private Stack minStack = new Stack<>();
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if (stack.pop().equals(minStack.peek())) minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}you can see we do not store all min vals but just changed min. So, my first idea was good 🙂 just needed some improvements.
But I’ve decided to find other solution 🙂 and did it… So, this is crazy solution based on one stack and this solution is accepted by leetcode
public class MinStack {
private Stack<Integer> internal = new Stack<Integer>();
int minVal = 0;
public void push(int x) {
if (internal.empty()) {
minVal = x;
internal.push(minVal);
internal.push(x);
} else if (minVal >= x) {
internal.push(minVal);
internal.push(x);
minVal = x;
} else {
internal.push(x);
}
}
public void pop() {
int x = internal.pop();
if (x == minVal) {
minVal = internal.pop();
}
}
public int top() {
return internal.peek();
}
public int getMin() {
return minVal;
}
}Oh, here is some magic based on the two methods push and pop. During push we are checking if input value is less than current minVal if yes, we are pushing current minVal to stack and input value if no, just input value. In pop we are reading top value from stack if that value is min, set next value from stack to min (look to the push for more understanding).
So, how that solution is really working? Try to understand it via our example:
-10 11 -7 -20 8
we are pushing these integers but internal stack will contain next elements:
-10 -10 11 -7 -10 -20 8
What can you see here, we are storing minVal in border case. Look to that list of elements and imagine next sequence of operations:
firstly you call getMin yes, minVal will be -20, good, next pop element (during pop you will check if you are deleting min element) now we have deleted 8, good, getMin will return -20. OK, call pop second time ,we are deleting -20 which current minimum, so, we should change minVal (reading next value from top we can see that next value is -10 perfect), all next pop and get min will work correctly because we handled border situation with deleting minimum (with loop solution we re-read minVal from stack).
Yes, generally last solution like prev one based on 2 stacks but more elegant for me 🙂
Thanks!
