1381. Design a Stack With Increment Operation

class CustomStack:

    def __init__(self, maxSize: int):
        self.st = []
        self.size = maxSize

    def push(self, x: int) -> None:
        if len(self.st) < self.size:
            self.st.append(x)

    def pop(self) -> int:
        if len(self.st)> 0:
            return self.st.pop()
        else:
            return -1

    def increment(self, k: int, val: int) -> None:
        for i in range(min(k,len(self.st))):
            self.st[i] += val

class CustomStack:
    """
    main idea: lazy increment 
    use an additional array (self.inc) to record increment value.  each time calling pop(), last item in self.inc need to add its value to its previous item before its popped out  
    """
    # tc O(1) sc O(1)
    def __init__(self, maxSize: int):
        self.st = []
        self.size = maxSize
        self.inc = [] # self.inc[i] :  accumutive sum from self.st[0] ~ self.st[i](inclusive)
    
    # tc O(1) sc O(N)
    def push(self, x: int) -> None:
        if len(self.st) < self.size:
            self.st.append(x)
            self.inc.append(0)
            
    # tc O(1) sc O(N)
    def pop(self) -> int:
        if not self.st : return -1 # here inc's size is actually same as st  
        if len(self.st) > 1:
            self.inc[-2] += self.inc[-1] # update second to last before popping last inc element out  
        return self.inc.pop() + self.st.pop()

        # tc O(1) sc O(N)
    def increment(self, k: int, val: int) -> None:
        if self.inc:
            self.inc[min(k,len(self.inc))-1] += val