Skip to content
Blog Python: Stack with Push, Pop and seek Minimum Value with O(1)

Python: Stack with Push, Pop and seek Minimum Value with O(1)

Pyhton 3 code to implement a stack with push, pop and seekMin function with time complexity of O(1)

class Stack:
    def __init__(self):
        self.items = []
        self.minList = []
        self.min = None
    
    def push(self, item):
        print("Push: ", item)
        self.items.append(item)
        if not self.min:
            self.min = item
        else:
            if item <= self.min:
                self.minList.append(self.min)
                self.min = item

        self.printAll()
    
    def pop(self):
        if self.items:
            item = self.items.pop()
            if item == self.min:
                self.min = self.minList.pop() if self.minList else None
            print("Pop: ", item)
                
            self.printAll()
            return item

        print("Pop: ", None)
                
        self.printAll()
        return None

    def seekMin(self):
        print("Min: ", self.min)
        return self.min

    def printAll(self):
        print('Items: ' , self.items)
        print('Min List: ' , self.minList)
        print('Min: ' , self.min)
        print()

stack = Stack()
stack.push(5)
stack.push(3)
stack.pop()
stack.push(2)
stack.push(2)
stack.push(4)
stack.push(7)
stack.push(3)
stack.pop()
stack.push(1)
stack.pop()
stack.pop()
stack.pop()

stack.seekMin()
dipin$ python3 2.py
Push:  5
Items:  [5]
Min List:  []
Min:  5

Push:  3
Items:  [5, 3]
Min List:  [5]
Min:  3

Pop:  3
Items:  [5]
Min List:  []
Min:  5

Push:  2
Items:  [5, 2]
Min List:  [5]
Min:  2

Push:  2
Items:  [5, 2, 2]
Min List:  [5, 2]
Min:  2

Push:  4
Items:  [5, 2, 2, 4]
Min List:  [5, 2]
Min:  2

Push:  7
Items:  [5, 2, 2, 4, 7]
Min List:  [5, 2]
Min:  2

Push:  3
Items:  [5, 2, 2, 4, 7, 3]
Min List:  [5, 2]
Min:  2

Pop:  3
Items:  [5, 2, 2, 4, 7]
Min List:  [5, 2]
Min:  2

Push:  1
Items:  [5, 2, 2, 4, 7, 1]
Min List:  [5, 2, 2]
Min:  1

Pop:  1
Items:  [5, 2, 2, 4, 7]
Min List:  [5, 2]
Min:  2

Pop:  7
Items:  [5, 2, 2, 4]
Min List:  [5, 2]
Min:  2

Pop:  4
Items:  [5, 2, 2]
Min List:  [5, 2]
Min:  2

Min:  2

Hope it helps.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.