# Shortest and fastest 1-stack and 2-stack solutions

• 2-stack solution may use less memory (ironically) since we don't save the 'min' for every pushed element.
If there are a lot of repeated elements, we may save even more memory by introducing a 'count' for each 'min'.

Cannot use vector (will get memory limit error), as vector doubles its capacity when full, whereas deque has a better capacity management strategy.

2 deque:

``````    deque<int> stack;
deque<int> mins;

void push(int x) {
int themin = mins.size() ? mins.back() : x;
stack.push_back(x);
if (x<=themin)
mins.push_back(x);
}

void pop() {
if (stack.back()==mins.back())
mins.pop_back();
stack.pop_back();
}

int top() {
return stack.back();
}

int getMin() {
return mins.back();
}
``````

1 deque (save current min for every pushed elem):

``````typedef pair<int,int> pairt;

deque<pairt> stack;

void push(int x) {
if (stack.size())
stack.push_back(make_pair(x, min(x,getMin()) ));
else
stack.push_back(make_pair(x, x));
}

void pop() {
stack.pop_back();
}

int top() {
return stack.back().first;
}

int getMin() {
return stack.back().second;
}``````

• I like this more than other solutions! Thanks for sharing!

• I got MLE for the 1-deque solution. I think it almost doubles the memory.

• I agree.1-deque solution wastes the momory.

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