155. Min Stack

155. Min Stack Solution programming interview question.

Design a stack that can return the minimum element in constant time and also support pus, pop and top methods.

Example:
Input
[“MinStack”,”push: -3″,”push: 0″,”push: -5″,”getMin”,”pop”,”top”,”getMin”]

Output
MinStack minStack = new MinStack();
minStack.push(-3); // returns null
minStack.push(0); // returns null
minStack.push(-5); // returns null
minStack.getMin(); // return -5
minStack.pop(); // returns null
minStack.top(); // return 0
minStack.getMin(); // return -3

Python 3 solution

Using 2 lists to keep the stack of all items and in parallel a stack with only the lowest values starting with inf and descending based on the inserted items during code execution.

Push only adds to second list if the last item in the minStack list is greater or equal to current item added.

Pop also removes the item form the minStack list if the current item is the same value as the latest item in the minStack list.

Returning the minStack value is literally returning the last item in the minStack list.

Test Code

import time
start_time = time.time()
def main():
    print("start")
    
    temp = MinStack()
    temp.push(-2)
    temp.push(0)
    temp.push(-3)
    temp.getMin() # return -3
    print("result minStack.getMin(): "+ str(temp.getMin()))
    temp.pop()
    temp.top()    # return 0
    temp.getMin() # return -2
    print("result minStack.top(): "+ str(temp.top()))
    print("result minStack.getMin(): "+ str(temp.getMin()))
    print("end")

class MinStack:

    def __init__(self):
        self.stack = []
        self.minstack = []
        self.minstack.append(float("inf"))
        print("self.stack: "+ str(self.stack))
        print("self.minstack: "+ str(self.minstack))

    def push(self, item: int) -> None:
        self.stack.append(item)
        if self.minstack[-1] >= item:
            self.minstack.append(item)
        print("push: -> self.stack: "+ str(self.stack))
        print("push: -> self.minstack: "+ str(self.minstack))

    def pop(self) -> None:
        p = self.stack.pop()
        if p == self.minstack[-1]:
            self.minstack.pop()
        print("pop: ^ self.stack: "+ str(self.stack))
        print("pop: ^ self.minstack: "+ str(self.minstack))
            
    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]

if __name__ == "__main__":
    main()
print("--- %s ms ---" % int(((time.time() - start_time)*1000)))

Test Output

start
self.stack: []
self.minstack: [inf]
push: -> self.stack: [-2]
push: -> self.minstack: [inf, -2]
push: -> self.stack: [-2, 0]
push: -> self.minstack: [inf, -2]
push: -> self.stack: [-2, 0, -3]
push: -> self.minstack: [inf, -2, -3]
result minStack.getMin(): -3
pop: ^ self.stack: [-2, 0]
pop: ^ self.minstack: [inf, -2]
result minStack.top(): 0
result minStack.getMin(): -2
end
>>> 

Solution Code

class MinStack:
    def __init__(self):
        self.stack = []
        self.minstack = []
        self.minstack.append(float("inf"))

    def push(self, item: int) -> None:
        self.stack.append(item)
        if self.minstack[-1] >= item:
            self.minstack.append(item)

    def pop(self) -> None:
        p = self.stack.pop()
        if p == self.minstack[-1]:
            self.minstack.pop()
            
    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]