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)?JollyJoker– JollyJoker2017-02-04 16:10:19 +00:00Commented Feb 4, 2017 at 16:10
Add a comment
|
2 Answers
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[0]:
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[0] == self._data[-1]:
del self._min_stack[0]
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[0]
if __name__ == '__main__':
obj = MinStack()
for i in [0,1,0]:
obj.push(i)
obj.getMin()
obj.pop()
obj.getMin()