[LeetCode 155] [Medium] Min Stack

Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initialises the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Solution

For each node that is pushed into the stack, we will keep a minValue tag on the current node to keep track of the minimum value that has been seen so far.

During the pop() operation, we need to check if the current stack is empty, if it is, we need to reset the stack. If the current element that is being pop out is the minimum value, then we will need to update the minimum value variable to the minValue tag associated with the next subsequent top element of the stack.

Code

class MinStack(object):

    def __init__(self):
        self.stack = []
        self.currentMinValue = float("inf")

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        # if the current value has a lower minimum value, 
        # update the minimum value tag for the current node

        self.currentMinValue = min(val, self.currentMinValue)
        self.stack.append([val, self.currentMinValue])

    def pop(self):
        """
        :rtype: None
        """
        print(self.stack)
        node = self.stack.pop()

        # if the stack is fully cleared during the pop(), 
        # reset the known min value back to inf
        if len(self.stack) == 0: 
            self.currentMinValue = float("inf") 
        # if the current min value is getting removed from the stack, 
        # we need to update the min value to the previous min value
        if self.currentMinValue == node[1]: 
            self.currentMinValue = self.stack[-1][1]
        

    def top(self):
        """
        :rtype: int
        """
        node = self.stack[-1]
        return node[0]

    def getMin(self):
        """
        :rtype: int
        """
        node = self.stack[-1]
        return node[-1]