DSA
Implement Min Stack
Stacks & Queues problem — solution with code and analysis.
Practice Link
Approach#
Store each element as a (value, currentMin) pair so the running minimum is tracked at every level of the stack. When pushing a new value, compare it with the current minimum (the second field of the top pair) and store the smaller of the two as the new running minimum. getMin() then simply returns the second field of the top pair in O(1) — no separate data structure or extra pass needed.
cpp
class MinStack {
public:
stack<pair<int,int>> stk;
MinStack() {
}
void push(int val) {
if(stk.empty())
stk.push({val,val});
else{
pair<int,int> temp = stk.top();
if(val < temp.second)
stk.push({val, val});
else
stk.push({val, temp.second});
}
}
void pop() {
stk.pop();
}
int top() {
return stk.top().first;
}
int getMin() {
return stk.top().second;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/