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]

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.

## Custom Stack Implementation with Increment Operation

This problem requires designing a custom stack data structure that supports standard stack operations like `push` and `pop`, but also includes an `increment` operation that adds a value to the bottom k elements of the stack.

### Naive Approach

A straightforward approach involves using an array or list to represent the stack.  The `push` and `pop` operations are standard array operations. The `increment` operation would iterate through the first `k` elements of the array and add the given value to each.

```python
class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.stack = []

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

    def pop(self) -> int:
        if self.stack:
            return self.stack.pop()
        else:
            return -1

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

Optimal Approach

The naive approach's increment operation has a time complexity of O(k), which can be inefficient if k is large and increment is called frequently. A more optimized solution uses an auxiliary array to store the increment values. This approach defers the actual increment until a pop operation occurs. This approach is more performant if increment is called more frequently than pop.

class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.stack = []
        self.increments = [0] * maxSize  # Auxiliary array to store increments

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

    def pop(self) -> int:
        if not self.stack:
            return -1

        index = len(self.stack) - 1
        val = self.stack.pop()
        
        # Add the increment value to the popped element
        val += self.increments[index]
        self.increments[index] = 0  # Reset the increment for this index

        return val

    def increment(self, k: int, val: int) -> None:
        limit = min(k, len(self.stack))
        if limit > 0:
             self.increments[limit-1] += val

Big(O) Run-time Analysis

• Naive Approach:
  • push: O(1)
  • pop: O(1)
  • increment: O(k) where k is the number of elements to increment
• Optimal Approach:
  • push: O(1)
  • pop: O(1)
  • increment: O(1)

The optimal approach significantly improves the increment operation's time complexity by using the auxiliary array. The increment operation just requires adding to the appropriate index in the array.

Big(O) Space Usage Analysis

• Naive Approach: O(maxSize) where maxSize is the maximum number of elements the stack can hold
• Optimal Approach: O(maxSize) where maxSize is the maximum number of elements the stack can hold. This is because we create an auxiliary array of the same size as the stack.

Both approaches require O(maxSize) space due to the stack itself. The optimal approach has an extra auxiliary array of the same size. Therefore, they both share the same Big(O) complexity when considering space.

Edge Cases

1. Stack Overflow: The push operation must check if the stack is full (reached maxSize) before adding an element.
2. Stack Underflow: The pop operation must check if the stack is empty before attempting to remove an element. The increment operation must handle cases where k is larger than the current stack size.
3. Zero Increment: If val is 0 in the increment operation, the operation should still execute without errors but effectively do nothing.

These edge cases are properly handled in the code snippets.