My Python solution using two lists beats 99.81% of python submissions


  • 0
    C
    class MinStack(object):
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            # store mins along with data, it takes some extra space, but provides O(1) access to the minimum element
            self.mins = [] 
            self.data = []
            
    
        def push(self, x):
            """
            :type x: int
            :rtype: void
            """
            # if we add the first element it is the minimum
            if len(self.data)==0: 
                self.mins.append(x)
            # if not, check whether the element being added is smaller than the current minimum element, if yes it is a new minimum element  
            else: 
                if x<self.mins[-1]:
                    self.mins.append(x)
                else:
                    self.mins.append(self.mins[-1]) # if not the previous element is still the minimum
            self.data.append(x)
            
    
        def pop(self):
            """
            :rtype: void
            """
            self.mins.pop(-1) # drop the last minimum
            return self.data.pop(-1)
            
            
    
        def top(self):
            """
            :rtype: int
            """
            return self.data[-1]
            
    
        def getMin(self):
            """
            :rtype: int
            """
            return self.mins[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.