Back to solutions

Min Stack

MediumStack & Queue

Design a stack supporting push, pop, top, and retrieving the minimum element, all in O(1).

Open problem
Constraints
  • At most 3 * 10^4 calls
  • -2^31 <= val <= 2^31 - 1

Auxiliary stack of running minima

Time O(1) per operationSpace O(n)

Keep a second stack whose top always holds the minimum of the elements currently in the main stack. Push the smaller of the new value and the current minimum; pop both stacks together.

#include <bits/stdc++.h>
using namespace std;

class MinStack {
    stack<int> st, mn;
public:
    void push(int val) {
        st.push(val);
        mn.push(mn.empty() ? val : min(val, mn.top()));
    }
    void pop() { st.pop(); mn.pop(); }
    int top() { return st.top(); }
    int getMin() { return mn.top(); }
};