~/leetcode $ 155. Min-Stack

Another classic question. First we need to notice that the ‘min’ value is only affected by the numbers that come before it. i.e. when we append something to the stack, it will not influence what value we pop when we pop things that came before it.

If we think about this, the min value that will be popped will be the minimum value of the stack. So for this data structure, we can keep track of two stacks: one for the actual values and another one for the min value.

When we append a value, we will also append the min value to the min stack, with the min value being whatever is less: the current element or the current top of the min stack.

class MinStack {
private:
    vector<int> stack;
    vector<int> minStack;
public:
    MinStack() {}

    void push(int value) {
        stack.push_back(value);
        if (minStack.empty()) {
            minStack.push_back(value);
        } else {
            int minValue = min(value, minStack.back());
            minStack.push_back(minValue);
        }
    }

    void pop() {
        stack.pop_back();
        minStack.pop_back();
    }

    int top() {
        return stack.back();
    }

    int getMin() {
        return minStack.back();
    }
};

Time Complexity: O(1)

Space Complexity: O(n)

Time Taken: 1m 32s