♾️155. Min Stack

Medium | Grid 75 | Wednesday 13, 2022

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

Implement the MinStack class:

• MinStack() initializes 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.

The biggest challenge about this question is having to return the minimum value in the stack. I couldn't think of a solution until I looked at the hints. The hint said, "Consider each node in the stack having a minimum value." Given this, I realized that you could have another stack that holds the minimum at the current level of our stack.

The solution below uses two stacks. One is the actual stack that we are asked to implement. The other is the min_stack which will hold the minimum value at each level of the stack.

def __init_ we initialize our stack as an empty list. We also initialize an empty minstack to store the level-wise minimum. Finally, we initialize our current minimum as infinite.

def push Whenever an element is pushed, we need to check if the current value (val) is smaller than the current minimum. We take the minimum of the pushed value and the curr_min and push that in our min_stack. Once pushed, we also need to update the curr_min value to the minimum.

def pop Whenever we pop from our main stack, we also pop from our min_stack. Once we pop from our min_stack we update our curr_min to the next element in the min_stack. CAUTION: We need to check if what we are popping is the last element in the main stack. After you pop, if there are no more elements, we need to reset the curr_min back to infinite.

def top We return the top most element in our main stack

def getMin We return the topmost element from our min_stack.

class MinStack:

    def __init__(self):
        self.stack = [] # actual stack
        self.min_stack = [] # min stack, every push pop will affect this stack as well 
        self.curr_min = float('inf') # our min value
       

    def push(self, val: int) -> None:
        self.stack.append(val) # append the value in the stack
        minimum = min(val, self.curr_min) # check if the value is less than the curren min
        self.min_stack.append(minimum) # append the minimum in our min stack
        self.curr_min = minimum # set the minimum as the current min
            
            
    def pop(self) -> None:
        self.stack.pop() # remove the top element
        self.min_stack.pop() # remove the top element from the min stack
        
        if not self.min_stack: 
            self.curr_min = float('inf') # set back min as inf when there are no more element
        else: 
            self.curr_min = self.min_stack[len(self.min_stack)-1] # reset the min as the next element in min stack
     

    def top(self) -> int:
        return self.stack[len(self.stack) - 1]
        

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

TIME AND SPACE COMPLEXITY

TIME: O(1) for each of the function.

SPACE: O(2N) where n is the number of elements at most.