ASAPUtils
The signal
This is a data-structure design problem: normal stack operations plus a global aggregate that must survive deletions. A single running minimum loses history. The missing information is the minimum that was true at the previous depth.
Approach ladder
1. Scan on every getMin() — O(n)
Push and pop are easy, but getMin walks all values. That violates the explicit O(1) requirement.
2. One global minimum — pop breaks it
If the values are [-2, 0, -3], the global minimum is −3. Pop −3 and you need to rediscover −2.
The past was discarded.
3. Store {value, minimumSoFar} — O(1) everything
class MinStack {
vector<pair<int,int>> st;
public:
void push(int val) {
int mn = st.empty() ? val : min(val, st.back().second);
st.push_back({val, mn});
}
void pop() { st.pop_back(); }
int top() { return st.back().first; }
int getMin() { return st.back().second; }
};
class MinStack {
constructor() { this.stack = []; }
push(value) {
const min = this.stack.length
? Math.min(value, this.stack.at(-1).min)
: value;
this.stack.push({ value, min });
}
pop() { this.stack.pop(); }
top() { return this.stack.at(-1).value; }
getMin() { return this.stack.at(-1).min; }
}
Why it works
At depth d, the stored minimum equals the minimum of all values from the bottom through d.
Pushing creates the next depth from min(newValue, previousMin). Popping reveals the previous
entry, which already carries the correct previous minimum. No state has to be recomputed.
Complexity
Every operation is O(1). The stack uses O(n) space and stores two integers per item. The constant-factor memory cost buys constant-time minimum queries.
Traps
- Updating a global minimum on push but having no restoration strategy on pop.
- In the two-stack variant, pushing only when
value < mininstead ofvalue <= min; duplicate minima then break when one is popped. - Overcomplicating this with a heap. A heap cannot delete the stack’s top value cleanly without extra bookkeeping.
Blank re-solve prompt
Implement Min Stack with pairs, then implement the two-stack variant. Explain how duplicate minimum values behave in both.