0

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

1
  • I assume you want the push and pop functions to remain O(1)? – JollyJoker Feb 4 '17 at 16:10
2

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.

0
1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.