1381. Design a Stack With Increment Operation

Design a stack that supports increment operations on its elements.

Implement the CustomStack class:

• CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
• void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
• int pop() Pops and returns the top of the stack or -1 if the stack is empty.
• void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1);                          // stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
stk.push(2);                          // stack becomes [1, 2]
stk.push(3);                          // stack becomes [1, 2, 3]
stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100);                // stack becomes [101, 102, 103]
stk.increment(2, 100);                // stack becomes [201, 202, 103]
stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
stk.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

• 1 <= maxSize, x, k <= 1000
• 0 <= val <= 100
• At most 1000 calls will be made to each method of increment, push and pop each separately.

Approach 01:

class CustomStack {
 public:
  CustomStack(int maxStackSize) : maxStackSize(maxStackSize) {}

  void push(int value) {
    if (stack.size() == maxStackSize)
      return;
    stack.push(value);
    pendingIncrements.push_back(0);
  }

  int pop() {
    if (stack.empty())
      return -1;
    const int stackIndex = stack.size() - 1;
    if (stackIndex > 0)
      pendingIncrements[stackIndex - 1] += pendingIncrements[stackIndex];
    const int returnValue = stack.top() + pendingIncrements[stackIndex];
    stack.pop();
    pendingIncrements.pop_back();
    return returnValue;
  }

  void increment(int count, int value) {
    if (stack.empty())
      return;
    const int lastIndex = min(count - 1, static_cast<int>(stack.size()) - 1);
    pendingIncrements[lastIndex] += value;
  }

 private:
  const int maxStackSize;
  stack<int> stack;
  vector<int> pendingIncrements;
};

class CustomStack:
    def __init__(self, maxStackSize: int):
        self.maxStackSize = maxStackSize
        self.stack = []
        self.pendingIncrements = []

    def push(self, value: int) -> None:
        if len(self.stack) == self.maxStackSize:
            return
        self.stack.append(value)
        self.pendingIncrements.append(0)

    def pop(self) -> int:
        if not self.stack:
            return -1
        stackIndex = len(self.stack) - 1
        if stackIndex > 0:
            self.pendingIncrements[stackIndex - 1] += self.pendingIncrements[stackIndex]
        returnValue = self.stack.pop() + self.pendingIncrements.pop()
        return returnValue

    def increment(self, count: int, value: int) -> None:
        if not self.stack:
            return
        lastIndex = min(count - 1, len(self.stack) - 1)
        self.pendingIncrements[lastIndex] += value

Time Complexity

• push(int value):

  Inserting an element at the top of the stack takes constant time, \(O(1)\), since it only involves checking the size, adding the element, and appending a 0 to the pendingIncrements vector.

• pop():

  Removing the top element of the stack and applying any pending increment takes constant time, \(O(1)\), because it adjusts the pending increments and pops the top element. Both operations involve only a few pointer/index manipulations.

• increment(int count, int value):

  Updating the increments for the bottom count elements takes constant time, \(O(1)\), as it directly modifies a value in the pendingIncrements vector without iterating over the entire stack. The logic only checks the last index that should be incremented.

• Overall Time Complexity:

  All operations (push, pop, and increment) have a time complexity of \(O(1)\) each.

Space Complexity

• Auxiliary Space:

  The main space consumption comes from the internal stack and the pendingIncrements vector. Both grow linearly with the number of elements in the stack, which is bounded by maxStackSize. Therefore, the space complexity is \(O(n)\), where n is the number of elements in the stack, and in the worst case, \(n = maxStackSize\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of elements in the stack, and is bounded by the maximum size maxStackSize.