# [leetcode] Min Stack

### Min Stack

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.

tag: Stack, Data Structure

8/10/2015 update

The same approach as described below.

```class MinStack {
public:
stack<int> s;
stack<int> mins;
void push(int x) {
s.push(x);
if(mins.empty() || x <= mins.top()){
mins.push(x);
}
}

void pop() {
int val = s.top();
s.pop();
if(val == mins.top()){
mins.pop();
}
}

int top() {
return s.top();
}

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

Hints:

• Consider space-time tradeoff. How would you keep track of the minimums using extra space?
• Make sure to consider duplicate elements.

#### O(n) runtime, O(n) space – Extra stack:

Use an extra stack to keep track of the current minimum value. During the push operation we choose the new element or the current minimum, whichever that is smaller to push onto the min stack.

#### O(n) runtime, O(n) space – Minor space optimization:

If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.

```class MinStack {
public:
stack<int> data;
stack<int> min_data;
void push(int x) {
if(data.empty()){
data.push(x);
min_data.push(x);
}
else{
data.push(x);
if (x <= min_data.top()){//less or equal
min_data.push(x);
}
}
}

void pop() {
int x = data.top();
data.pop();
if(x == min_data.top()){
min_data.pop();
}
}

int top() {
return data.top();
}

int getMin() {
return min_data.top();
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.