Problem statement

https://binarysearch.com/problems/Incrementable-Stack/

Solution

Equal to Leetcode 1381. Design a Stack With Increment Operation.

Complexity

Time complexity of all operations is O(1), space is O(n).

Code

class IncrementableStack:
    def __init__(self):
        self.stack = [0]
        self.last = 0
        
    def append(self, x):
        self.stack += [x - self.last]
        self.last = x
        
    def pop(self):
        ans = self.last
        self.last -= self.stack.pop()
        return ans
        
    def increment(self, val, k):
        if k < len(self.stack) - 1:
            self.stack[1] += val
            self.stack[k + 1] -= val
        elif len(self.stack) > 1:
            self.stack[1] += val
            self.last += val