# Implementing additional function to stack data structure

How would i design a stack which in addition to `push()` and `pop()` ,also has a function min which returns the minimums element ? `min()` must operate in big O(1) time

• I assume you want the push and pop functions to remain O(1)? Feb 4, 2017 at 16:10

You need an additional stack of minimums. In `push`, if the new element is less than or equal to the top of the min-stack, push it there too. In `pop`, if the popped element is equal to the top of the minstack, pop it from there too.

As pointed out by others, you need to create another stack of minimums. Technically this would still be O(1), but its space would be multiplied by a constant factor of two. This is a python implementation using lists:

``````class Empty(Exception):
pass

class MinStack(object):

def __init__(self):
self._data = []
self._min_stack = []

def __len__(self):
return len(self._data)

def is_empty(self):
return len(self._data) == 0

def push(self, x):
if self.is_empty():
self._min_stack.append(x)
elif x <= self._min_stack:
self._min_stack.insert(0,x)
self._data.append(x)

def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
if self._min_stack == self._data[-1]:
del self._min_stack
return self._data.pop()

def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1]

def getMin(self):
return self._min_stack

if __name__ == '__main__':
obj = MinStack()
for i in [0,1,0]:
obj.push(i)
obj.getMin()
obj.pop()
obj.getMin()
``````