Design a Stack With Increment Operation

Problem Statement

In this problem, you are required to design a special kind of stack called CustomStack that not only performs the usual push and pop operations but can also increment a specified number of elements starting from the bottom of the stack. The CustomStack allows for the initialization with a maximum size, providing a limit to the number of elements it can hold. Elements are added to the top unless the stack has reached its maximum capacity. The pop operation will remove the top element and return its value or return -1 if the stack is empty. Additionally, the increment operation is required to increase the value of the bottom k elements by a given value val. If the stack contains fewer than k elements, then all elements will be incremented.

Examples

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 and Intuition

The problem requires a stack with enhanced functionality. Here's a step-by-step breakdown of how the operations are handled:

1. Initialization:

   • The CustomStack is initialized with a maximum size, maxSize. This size prevents more than maxSize elements from being added to the stack.

2. Push Operation:

   • Before adding a new element to the stack with the push operation, check if the current size of the stack is less than maxSize.
   • If true, add the element to the top of the stack.

3. Pop Operation:

   • Check if the stack is not empty before popping.
   • If the stack is empty, return -1.
   • If not, remove the top element from the stack and return its value.

4. Increment Operation:

   • This operation adds more complexity. It requires incrementing the bottom k elements of the stack by a value val.
   • If k is greater than the current size of the stack, then all elements in the stack should be incremented.
   • Otherwise, only the bottom k elements are incremented.

By understanding these operations, we can maintain the stacking order and ensure the additional increment functionality does not disrupt the primary operations of push and pop. The design ensures efficiency and simplicity, keeping track of current size and applying increments directly to elements in the stack without additional structures. This approach also considers performance constraints, ensuring that each operation can handle up to 1000 calls efficiently.

Solutions

class EnhancedStack {
private:
    vector<int> dataStack;
    vector<int> lazyIncrement;
    int stackTop;
    
public:
    EnhancedStack(int maxSize) {
        dataStack.resize(maxSize);
        lazyIncrement.resize(maxSize);
        stackTop = -1;
    }
    
    void push(int x) {
        if (stackTop < (int)(dataStack.size()) - 1) {
            dataStack[++stackTop] = x;
        }
    }
    
    int pop() {
        if (stackTop == -1) {
            return -1;
        }
    
        int value = dataStack[stackTop] + lazyIncrement[stackTop];
    
        if (stackTop > 0) {
            lazyIncrement[stackTop - 1] += lazyIncrement[stackTop];
        }
    
        lazyIncrement[stackTop] = 0;
        stackTop--;
        return value;
    }
    
    void addIncrement(int k, int val) {
        if (stackTop >= 0) {
            int limit = min(stackTop, k - 1);
            lazyIncrement[limit] += val;
        }
    }
};