Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost.

public class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MinStack() {
        // do initialize if necessary
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    public void push(int number) {
        // write your code here
        stack1.push(number);
        if (stack2.isEmpty() || number <= stack2.peek()) {
            stack2.push(number); //bug <=, we also push element when it's equal to the min number so far, since we might have duplicate min numbers
        }
    }

    public int pop() {
        // write your code here
        int toRemove = stack1.pop();
        if (toRemove == stack2.peek()) {
            stack2.pop();
        }
        return toRemove;
    }

    public int min() {
        // write your code here
        return stack2.peek();
    }
}

class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = None

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if self.min is None or self.min >= x:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self):
        """
        :rtype: void
        """

        ret = self.stack.pop()
        if ret == self.min:
            self.min = self.stack.pop()
        return ret

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min

class MinStack {
public:
    stack<int> nums;
    MinStack() {
    }

    void push(int val) {
        if (nums.empty() || nums.top() >= val) {
            nums.push(val);
            nums.push(val);
        } else {
            int tmp = nums.top();
            nums.push(val);
            nums.push(tmp);
        }
    }

    void pop() {
        nums.pop();
        nums.pop();
    }

    int top() {
        int tmp1 = nums.top();
        nums.pop();
        int tmp2 = nums.top();
        nums.push(tmp1);
        return tmp2;
    }

    int getMin() {
        return nums.top();
    }
    };