[Top Interview 150] 155. Min Stack

Solution)

 

class MinStack:
    def __init__(self):
        self.stack = []
        self.minVal = float('inf')
        
    def push(self, val: int) -> None:
        # Append a tuple in a form of (val, previous minVal)
        self.stack.append((val, self.minVal))
        
        # Update minVal if need to
        self.minVal = min(self.minVal, val)
        

    def pop(self) -> None:
        # When we pop, we might pop a tuple that has a value of minVal
        # so we update minVal to a previous minVal just in case
        self.minVal = self.stack.pop()[1]

    def top(self) -> int:
        # return the value of top tuple
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.minVal

 
 
Problem: LeetCode
 
Time Complexity: O(1)
Space Complexity: O(n)
 
 

Explanation)

 
When the class object is initialized, we'll have a list and an int variable. List will save the values as they're pushed, and the int variable will save the current minimum value of the stack.
 
As we push the values in the list, we'll save them in a form of tuple (val, previous minVal). We save the previous minVal together in a tuple so that when the current minVal is popped, we still know what the second minimum value is. 
 
If the reason why we're using a tuple doesn't make sense, just keep in mind that we're using the format of tuples to save the values for now.
 
 

Initialization)

 
Our stack will initially be an empty list.
 
Our int variable minVal will save the current minimum value in stack. Initially we'll have a positive infinity so that our first value will automatically become the next minVal.
 

class MinStack:
    def __init__(self):
        self.stack = []
        self.minVal = float('inf')

 
 

push)

 
As said earlier, when we push a new value to stack, we'll push a tuple in the form of (value, previous minVal).
 
Once pushed, the new value might be our minimum value thus we try to update minVal.
 
 
MinStack    ->     push(0)    ->        push(-1)
      [ ]          ->     [(0, inf)]    ->   [(0, inf), (-1, 0)]
MinVal=inf   ->   MinVal=0   ->     MinVal=-1
 

class MinStack:
    def __init__(self):
        self.stack = []
        self.minVal = float('inf')

    def push(self, val: int) -> None:
        self.stack.append((val, self.minVal))
        self.minVal = min(self.minVal, val)

 
 

Pop)

 
For normal stacks, we'll simply pop() from a list and finish.
 
For this class, we have one more step of updating minVal. If our popped tuple had a value of minVal, our minimum value in stack now has changed. So to update our changed minVal, we'll set our minVal as the previous minVal.
 
     MinStack         ->      pop()     
[(0, inf), (-1, 0)]     ->     [(0, inf)]    
  minVal = -1        ->   minVal = 0
 
OR
 
     MinStack         ->      pop()   
[(-1, inf), (-1, -1)]     ->     [(-1, inf)]    
  minVal = -1        ->   minVal = -1
 

class MinStack:
    def __init__(self):
        # Initialization
        
    def push(self, val: int) -> None:
        self.stack.append((val, self.minVal))
        self.minVal = min(self.minVal, val)      

    def pop(self) -> None:
        self.minVal = self.stack.pop()[1]

  
 

top and getMin)

 
Once we have the logic working in push() and pop(), the rest is easy because we don't affect or change stack.
 
So for top(), we return the value on -1st tuple.
for getMin(), we return minVal.
 
Very easy!
 

class MinStack:
    def __init__(self):
        # Initialization

    def push(self, val: int) -> None:
        # Push
  
    def pop(self) -> None:
        self.minVal = self.stack.pop()[1]

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

    def getMin(self) -> int:
        return self.minVal

 
 
 
Even when I had the glimpse of how to code this, it took me a bit of time to make them work. Constructing a class is definitely one of my favorite LeetCode problems. It requires simple logic but clever approach.