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]

Related Guides and Helpful Resources

If you found this guide helpful, check out these related step-by-step tutorials and category resources on ION HowTo:

• How to Replace AC Remote Batteries with a Ballpoint Pen: Lever out stubborn AAA batteries from deep remote slots without tools.
• Clean USB-C Port with Paper: Simple household trick to clean lint and debris from loose charging ports safely.
• IKEA KOPLA B22 to E27 Socket Converter Guide: Convert older UK bayonet lamp fittings to fit modern screw-in LED bulbs.
• DIY Hacks and Life Solutions: Explore our full collection of tutorials and step-by-step articles in this category.