Problem Explanation

We are required to implement the CustomStack class which would allow us to perform certain operations on a stack. The operations are as follows:

1. CustomStack(int maxSize): Initializes the object with maxSize which determines the maximum number of elements in the stack or do nothing if the stack reached maxSize.

2. void push(int x): Adds an integer x to the top of the stack if the stack hasn't reached maxSize.

3. int pop(): Pops and returns the top of stack or returns -1 if the stack is empty.

4. void increment(int k, int val): Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, all the elements in the stack are incremented.

For instance, let's consider the following example:

1
2
3Input
4["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
5[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
6Output
7[null,null,null,2,null,null,null,null,null,103,202,201,-1]

Here, we initialize the stack with a maxSize of 3. Then we perform the operations in the order given in the input. The operations perform as follows:

• After the first two push operations, the stack becomes [1,2].
• On pop operation, it returns the top of the stack which is 2 and the stack becomes [1].
• After the next three push operations , the stack becomes [1,2,3]. The push operation which tries to push 4 does nothing as the stack already reached maxSize.
• On the first increment operation, all the elements in the stack are incremented by 100 as k > current size of stack. So, [1,2,3] becomes [101,102,103].
• On the second increment operation, the bottom two elements are incremented by 100. So, [101,102,103] becomes [201,202,103].
• On the next three pop operations, it pops the top elements in the stack and returns them. Hence, it returns 103, 202, and 201 in that order.
• On the last pop operation, it returns -1 as the stack is empty by then.

Walkthrough of the solution

The solution uses two separate data containers - a stack and a vector. The stack is used to store the elements while the vector is used to keep track of pending increments where pendingIncrements[i] indicates the increment needed for all elements at and below index i in the stack.

• For the push operation, we first check whether the current size of the stack is less than the maxSize. If it is, we proceed to push the element into both stack and the pendingIncrements with pendingIncrements pushed with 0.

• For the pop operation, if the stack is empty, we return -1. Otherwise, we store the top element of the stack, pop the element and return it as the output of the pop operation. While doing this, if there are increments that are pending for the top element, we propagate it to the next top element and then proceed with the pop operation.

• For the increment operation, we find out how many elements have to be incremented by taking the minimum of k and the current size of the stack. Then we add val to the respective index in the pendingIncrements.

Solution

Python

1
2python
3class CustomStack:
4
5    def __init__(self, maxSize: int):
6        self.stack = []
7        self.maxSize = maxSize
8        self.pendingIncrements = []
9
10    def push(self, x: int) -> None:
11        if len(self.stack) == self.maxSize:
12            return
13        self.stack.append(x)
14        self.pendingIncrements.append(0)
15
16    def pop(self) -> int:
17        if not self.stack:
18            return -1
19        i = len(self.stack) - 1
20        if i != 0:
21            self.pendingIncrements[i - 1] += self.pendingIncrements[i]
22        res = self.stack[-1] + self.pendingIncrements[i]
23        self.stack.pop()
24        self.pendingIncrements.pop()
25        return res
26
27    def increment(self, k: int, val: int) -> None:
28        if not self.stack:
29            return
30        i = min(k - 1, len(self.stack) - 1)
31        self.pendingIncrements[i] += val

Java

1
2java
3class CustomStack {
4    private int maxSize;
5    private int top;
6    private int[] stack;
7    private int[] incr;
8
9    public CustomStack(int maxSize) {
10        this.maxSize = maxSize;
11        this.stack = new int[maxSize];
12        this.incr = new int[maxSize];
13        this.top=-1;
14    }
15
16    public void push(int x) {
17        if (top != maxSize - 1) {
18            top++;
19            stack[top] = x;
20        }
21    }
22
23    public int pop() {
24        if (top == -1) {
25            return -1;
26        }
27        int increment = incr[top];
28        if (top > 0) incr[top - 1] += increment;
29        incr[top] = 0;
30        return stack[top--] + increment;
31    }
32
33    public void increment(int k, int val) {
34        int idx = Math.min(k, top + 1) - 1;
35        if (idx >= 0) incr[idx] += val;
36    }
37}

JavaScript

1
2javascript
3class CustomStack {
4    constructor(maxSize) {
5        this.stack = [];
6        this.maxSize = maxSize;
7        this.incrementList = Array(maxSize).fill(0);
8    }
9    
10    push(x) {
11        if (this.stack.length < this.maxSize) {
12            this.stack.push(x);
13            this.incrementList[this.stack.length] = 0;
14        }
15    }
16    
17    pop() {
18        if (this.stack.length === 0) {
19            return -1;
20        }
21        
22        const val = this.stack.pop() + this.incrementList[this.stack.length + 1];
23        this.incrementList[this.stack.length] += this.incrementList[this.stack.length + 1];
24        this.incrementList[this.stack.length + 1] = 0;
25        return val;
26    }
27    
28    increment(k, val) {
29        k = Math.min(k, this.stack.length);
30        this.incrementList[k - 1] += val;
31    }
32}

C++

1
2c++
3class CustomStack {
4public:
5    int top;
6    vector<int> pendingIncrements, stack;
7    
8    CustomStack(int maxSize) {
9        top = maxSize;
10        stack.resize(top);
11        pendingIncrements.resize(top);
12        fill(pendingIncrements.begin(),pendingIncrements.end(),0);
13    }
14    
15    void push(int x) {
16        if(pendingIncrements.size() < top){
17            stack[pendingIncrements.size()] = x;
18            pendingIncrements.push_back(0);
19        }
20    }
21    
22    int pop() {
23        if(!pendingIncrements.size())
24            return -1;
25        if(pendingIncrements.size() > 1)
26            pendingIncrements[pendingIncrements.size()-2] += pendingIncrements[pendingIncrements.size()-1];
27        int ans = stack[pendingIncrements.size()-1] + pendingIncrements[pendingIncrements.size()-1];
28        pendingIncrements.pop_back();
29        return ans;
30    }
31    
32    void increment(int k, int val) {
33        if(pendingIncrements.size())
34            pendingIncrements[min(k, (int)pendingIncrements.size()) - 1] += val;
35    }
36};

C#

1
2csharp
3public class CustomStack {
4    private readonly int maxSize;
5    private int top;
6    private readonly int[] stack;
7    private readonly int[] increment;
8
9    public CustomStack(int maxSize) {
10        this.maxSize = maxSize;
11        this.stack = new int[maxSize];
12        this.increment = new int[maxSize];
13        this.top = -1;
14    }
15    
16    public void Push(int x) {
17        if (top+1 < maxSize){
18            stack[++top] = x;
19        }
20    }
21    
22    public int Pop() {
23        if (top == -1){
24            return -1;
25        }
26        var incrementTotal = increment[top];
27        if (top != 0){
28            increment[top - 1] += increment[top];
29        }
30        increment[top] = 0;
31        return stack[top--] + incrementTotal;
32    }
33    
34    public void Increment(int k, int val) {
35        var length = Math.Min(k, top + 1);
36        if (length > 0){
37            increment[length - 1] += val;
38        }
39    }
40}

In the code snippet provided, we defined a class 'CustomStack' and initialized it with 'maxSize'. We implemented push, pop, and increment methods in the class. In the push method, we first checked if the stack size is less than maxSize, and if it is, we pushed the element into both stack and the 'pendingIncrements'. In the pop method, we checked if the stack is empty, if yes, we returned -1 else we performed the operation. The increment method checks if there's any element in the stack and then performs increment operation.

These code snippets above reflect four popular programming languages: Python, Java, JavaScript, C++, and C#. This problem is a wonderful example of how we can use the fundamental concept of stacks to solve real-life problems.

Even though the syntaxes of these languages are different, the fundamental approach to solving the problem remains the same. This goes to show the universal nature of algorithmic problem-solving – if you can solve a problem in one language, you can solve it in any language! Happy coding.