Retrieve min from stack in O(1) 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 &lt; 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()
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 &lt;module&gt;
    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 &lt;= 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).