7
\$\begingroup\$

I have written a stack in Python that is required to push, pop and return the minimum of the stack in \$O(1)\$ time.

#!python3
class Stack():
    def __init__(self):
        self.items = []
        self.min = None

    def push(self, item):
        self.items.append(item)
        self.minimum()

    def pop(self):
        if self.isEmpty():
            raise ValueError('Empty stack')
        else:
            return self.items.pop()

    def minimum(self):
        if self.min is None:
            self.min = self.peek()
        else:
            if self.peek() < self.min:
                self.min = self.peek()

    def getMinimum(self):
        return self.min

    def peek(self):
        try:
            return self.items[-1]
        except IndexError as e:
            print(e)

    def size(self):
        return len(self.items)

    def isEmpty(self):
        return self.size() == 0

stack = Stack()

nums = [6,4,8,9,1,5,2,3]
for i in nums:
    stack.push(i)

print(stack.getMinimum())

What I have tried to do is, compare the current minimum with each new addition to the stack so that the

self.min

attribute constantly updates.

Eventually, to get the minimum, I simply call the

self.getMinimum()

function to return the minimum. My question is, does this actually occur in \$O(1)\$ time?

\$\endgroup\$
4
\$\begingroup\$

You can correctly implement the stack with minimum query by maintaining a second array that holds current minimum on its top. When you push the very first element, you append it to both the arrays. Next, when you push the subsequent element \$e\$, you append it to the actual stack array as is, but you push \$\min \{ e, e' \}\$ to the minimum stack, where \$e'\$ is the top element of the minimum stack. Popping is trivial: just pop both the actual element array and the minimum array. All in all, it might look like this:

class Stack():

    def __init__(self):
        self.element_stack = []
        self.min_element_stack = []

    def push(self, item):
        if self.size() == 0:
            self.min_element_stack.append(item)
        else:
            self.min_element_stack.append(min(self.min_element_stack[self.size() - 1], item))
        self.element_stack.append(item)

    def pop(self):
        if self.is_empty():
            raise ValueError('Empty stack')
        self.min_element_stack.pop()
        return self.element_stack.pop()

    def minimum(self):
        if self.is_empty():
            raise ValueError('Empty stack')
        return self.min_element_stack[self.size() - 1]

    def is_empty(self):
        return self.size() == 0

    def size(self):
        return len(self.element_stack)


def main():
    stack = Stack()
    stack.push(3)
    print(stack.minimum())
    stack.push(5)
    print(stack.minimum())
    stack.push(1)
    print(stack.minimum())
    stack.pop()
    print(stack.minimum())

if __name__ == "__main__":
    main()

Hope that helps.

\$\endgroup\$
6
\$\begingroup\$

The minimum gets updated after a push but not after a pop, causing getMinimum to return the wrong value:

>>> stack = Stack()
>>> stack.push(2)
>>> stack.push(1)
>>> stack.getMinimum()
1 # correct
>>> stack.pop()
1
>>> stack.getMinimum()
1 # wrong: the only item in the stack now is the number 2
\$\endgroup\$
1
\$\begingroup\$
  • In Python 3, a class is typically not declared with parentheses (Python 2 required deriving classes from object: class A(object), however this isn't the case in Python 3).

  • Shebangs should be #!/usr/bin/env python3 for Python 3.

  • If I am not mistaken, this is in fact \$ O(1) \$, since it is not influenced by the size of the stack.

\$\endgroup\$

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.