LeetCode: Min Stack

LeetCode Challenge Description: 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;
public:
    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() {
        s.pop();
    }
    
    int top() {
        pair<int, int> t = s.top();
        return t.first;
    }
    
    int getMin() {
        pair<int, int> t = s.top();
        return t.second;
    }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← Intersection of Two Linked Lists LeetCode: Word Search →