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()

• CodesInChaos: Your requirements sound impossible to me unless you make some additional assumptions. Proof: The optimal comparison sorting algorithm (given a simple comparer and nothing more) has runtime Ω(n*log(n)). If you push all elements and then use alternating calls to min and pop you get back a sorted list in time O(n), which is a contradiction. => The only way to have O(1) for all of push, pop and min is going beyond a simple comparer.
• Janne Karila: @CodesInChaos No, you can't use this for sorting because there is no function to pop the minimum off the stack.

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.

• Jaime: Even with the integers only restriction, the operations are not always O(1): when the counting bin of your minimum gets to 0 you need to search for the new minimum, which is going to be an O(n) operation.
• La-comadreja: read the answer again. Not with a 2nd stack which is sorted and contains one element per value contained in the stack.
• Janne Karila: How would you maintain the array in sorted order with constant time push and pop?