Retrieve min from stack in O(1)

Question

I wrote some Python code to solve the following problem. I'm curious to see if someone else can find a better solution, or critique my solution.

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

class SmartStack:
    def __init__(self):
        self.stack= []
        self.min = []

    def stack_push(self,x):
        self.stack.append(x)
        if len(self.min) != 0:
            if x < self.stack_min():
                self.min.append(x)
        else:
            self.min.append(x)

    def stack_pop(self):
        x = self.stack.pop()
        if x == self.stack_min():
            self.min.pop()
        return x

    def stack_min(self):
        return self.min[-1]

def main():
    print "Push elements to the stack"
    list = range(10)
    stack = SmartStack()
    for i in list:
        stack.stack_push(i)
    print "Print stack and stack minimum"
    print stack.stack
    print stack.stack_min()
    print "Push -1 to stack, print stack and stack minimum"
    stack.stack_push(-1)
    print stack.stack
    print stack.stack_min()
    print "Pop from stack, print stack and stack minimum"
    print stack.stack_pop()
    print stack.stack
    print stack.stack_min()

if __name__ == "__main__":
    main()

Answer 1

Your implementation fails if there are duplicates values in the stack:

def main():
    stack = SmartStack()
    stack.stack_push(1)
    stack.stack_push(1)
    stack.stack_push(3)
    stack.stack_pop()
    stack.stack_pop()
    print(stack.stack_min())

$ ./smartstack 
Traceback (most recent call last):
  File "./smartstack", line 35, in <module>
    main()
  File "./smartstack", line 32, in main
    print(stack.stack_min())
  File "./smartstack", line 23, in stack_min
    return self.min[-1]
IndexError: list index out of range

Suggested fix:

def stack_push(self,x):
    self.stack.append(x)
    if not self.min or x <= self.stack_min():
        self.min.append(x)

The naming is redundant: methods of the SmartStack class shouldn't need to have "stack_" in their names.

If you are targeting Python 2, be sure to use new-style classes (i.e., SmartStack should have object as a superclass).

Answer 2

Your code will not return min value when you pop from stack. The "min" stack is not properly maintained. if the value to be inserted is not smaller than the one in min stack, you have to insert the "min.append(self.stack_min())". Please change the following for it to work as expected. Suggested fix:

    else:
        self.min.append(self.stack_min())

Answer 3

This assumes your stack has integer values, or values that can be translated in constant time to integers. If you're creating the stack from scratch and building the class yourself, create an array of integers where the indices are the values of the elements, and the values at those indices are the number of elements in the stack with those values. Also create another stack representing the set of number values, sorted with the lowest values in front. Then push() of a new min also adds an element to the new stack, pop() of the lowest value is also a pop of the new stack. I do think you need another data structure to keep track of the sorting in constant time.