educative.io

How is two stacks a viable a solution?

Courses
, ,
#1

Couldn’t you simply keep track of the smallest value while pushing items into the stack? This is for the problem “Challenge 9: min( ) Function Using a Stack”.

class MinStack:
    def __init__(self):
        self.min_value = None
        self.stack = []

    def pop(self):
        self.stack.pop()

    def push(self, value):
        if not self.min_value or value < self.min_value:
            self.min_value = value

        self.stack.append(value)

    def min(self):
        return self.min_value
#2

Same here, the author’s implementation is space of O(n+m) and two stacks add unneeded complexity, in your solution, pop() has to check if the popped out value is the min value, in this case, it should find the next min which is o(n), one more thing, if you inherited from the mystack, you can use push and pop there to implement the functionality , you can just initialise min_value to float(‘inf’) and the check in push will take care of keeping the value correct. Inspired from minheap implementation in Robert Sedgewick book