LeetCode: Min Stack

Solution with Stack

Note the requirement of retrieving the minimum element in constant time. For this purpose, we need to use a extra space to store the current minimum element with different top values in in the stack.

#include <stack>
using namespace std;

class MinStack {
    stack<pair<int, int> > s;
    MinStack() { }        

    void push(int x) {
        if(s.empty()) {
            s.push(std::make_pair(x, x));
        } else {
            int n = min(x, getMin());
            s.push(std::make_pair(x, n));

    void pop() {

    int top() {
        pair<int, int> t = s.top();
        return t.first;

    int getMin() {
        pair<int, int> t = s.top();
        return t.second;

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *