# Design a Stack With Increment Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-a-stack-with-increment-operation)
Canonical: https://scaleengineer.com/dsa/problems/design-a-stack-with-increment-operation
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Stack
**Companies:** [eBay](https://scaleengineer.com/companies/ebay), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Moloco](https://scaleengineer.com/companies/moloco), [IMC](https://scaleengineer.com/companies/imc)
---
## Problem
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.

# Approaches
## Naive Approach with Direct Iteration
This approach uses a simple array or list to simulate the stack. The `push` and `pop` operations work as they would in a standard array-based stack implementation. The `increment` operation is handled by directly iterating through the bottom `k` elements of the array and adding the value `val` to each one.
**Time:** - **`push()`**: O(1) - Constant time array access.
- **`pop()`**: O(1) - Constant time array access.
- **`increment()`**: O(k) - In the worst case, we iterate through `k` elements, which can be up to `maxSize`. So, it's O(maxSize). · **Space:** O(maxSize) - We need an array of size `maxSize` to store the stack elements.
**Pros:** Simple to understand and implement.; Uses a standard array, which is memory-efficient.
**Cons:** The `increment` operation is inefficient, with a time complexity linear to `k`. This can be slow if `k` is large and `increment` is called frequently.
### Explanation
In this method, we use a standard array to represent the stack's data. A pointer, `top`, keeps track of the current size and the position for the next push.

- The `push` and `pop` methods are implemented in the standard O(1) time complexity for an array-based stack.
- The `increment(k, val)` method is the most straightforward part. It loops through the first `k` elements of the array (or fewer if the stack size is less than `k`) and adds `val` to each. This makes the `increment` operation's performance dependent on the value of `k`.

```java
class CustomStack {
    private int[] stack;
    private int top;
    private int maxSize;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
        this.top = -1;
    }

    public void push(int x) {
        if (top < maxSize - 1) {
            top++;
            stack[top] = x;
        }
    }

    public int pop() {
        if (top == -1) {
            return -1;
        }
        int val = stack[top];
        top--;
        return val;
    }

    public void increment(int k, int val) {
        int limit = Math.min(k, top + 1);
        for (int i = 0; i < limit; i++) {
            stack[i] += val;
        }
    }
}
```
### Algorithm
- Initialize an integer array `stack` of size `maxSize` to store the elements.
- Maintain an integer `top` to point to the index of the top element, initialized to -1.
- **`push(x)`**: If the stack is not full (`top < maxSize - 1`), increment `top` and place `x` at `stack[top]`.
- **`pop()`**: If the stack is not empty (`top >= 0`), return the element at `stack[top]` and then decrement `top`. Otherwise, return -1.
- **`inc(k, val)`**: Iterate from index `i = 0` up to `min(k - 1, top)`. In each iteration, add `val` to `stack[i]`. This directly modifies the values of the bottom elements.

## Optimized Approach with Lazy Increment
This approach avoids the costly iteration in the `increment` method by deferring the additions. It uses an auxiliary array to store the increments, making the `increment` operation O(1). The actual value of an element is calculated only when it is popped from the stack.
**Time:** - **`push()`**: O(1) - Constant time.
- **`pop()`**: O(1) - Constant time.
- **`increment()`**: O(1) - Constant time. All operations are now highly efficient. · **Space:** O(maxSize) - We use two arrays, `stack` and `inc`, both of size `maxSize`. The total space is `O(2 * maxSize)`, which simplifies to O(maxSize).
**Pros:** Extremely efficient, with all operations taking constant time.; Scales well regardless of the number of calls or the value of `k`.
**Cons:** Requires extra space for the increment array, doubling the storage requirement compared to the naive approach.; The logic is slightly more complex to understand due to the deferred nature of the increment operation.
### Explanation
To optimize the `increment` operation, we can avoid iterating through the elements. The core idea is to use a lazy update mechanism. We maintain a second array, let's call it `inc`, of the same size as the stack.

- `inc[i]` will store the total increment value that needs to be applied to `stack[i]` and all elements below it.
- When `increment(k, val)` is called, instead of adding `val` to `k` elements, we simply add `val` to `inc[k-1]` (or the top-most valid index). This marks that the element at this position and everything below it has an additional `val` to be added.
- When `pop()` is called for the element at `top`, we calculate its true value by adding `stack[top] + inc[top]`. Then, we propagate the increment downwards by adding `inc[top]` to `inc[top-1]`. This ensures the element below will correctly account for the increment when it is popped. This makes all operations O(1).

```java
class CustomStack {
    private int[] stack;
    private int[] inc; // Stores lazy increments
    private int top;
    private int maxSize;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
        this.inc = new int[maxSize];
        this.top = -1;
    }

    public void push(int x) {
        if (top < maxSize - 1) {
            top++;
            stack[top] = x;
            inc[top] = 0; // Reset increment for new element
        }
    }

    public int pop() {
        if (top == -1) {
            return -1;
        }
        
        int incrementValue = inc[top];
        int result = stack[top] + incrementValue;
        
        // Pass the increment down to the element below
        if (top > 0) {
            inc[top - 1] += incrementValue;
        }
        
        top--;
        
        return result;
    }

    public void increment(int k, int val) {
        if (top == -1) {
            return;
        }
        // The increment applies to elements from index 0 to min(k, size)-1.
        // We only need to add the increment to the top-most affected element's slot.
        int limitIndex = Math.min(k - 1, top);
        inc[limitIndex] += val;
    }
}
```
### Algorithm
- Initialize a value array `stack`, an auxiliary increment array `inc` of the same size, and a `top` pointer.
- **`push(x)`**: If not full, increment `top`, set `stack[top] = x`, and ensure `inc[top]` is 0.
- **`increment(k, val)`**: If the stack is not empty, find the index of the top-most element to be incremented, `idx = min(k-1, top)`. Add `val` to `inc[idx]`. This is an O(1) step.
- **`pop()`**: If not empty, get the total increment for the top element: `increment_value = inc[top]`. Calculate the final value: `result = stack[top] + increment_value`. Before popping, pass the increment down to the element below: `inc[top-1] += increment_value` (if `top > 0`). Reset `inc[top] = 0`, decrement `top`, and return `result`.

# Solutions
### Java

```java
class CustomStack { private int [] stk ; private int [] add ; private int i ; public CustomStack ( int maxSize ) { stk = new int [ maxSize ]; add = new int [ maxSize ]; } public void push ( int x ) { if ( i < stk . length ) { stk [ i ++] = x ; } } public int pop () { if ( i <= 0 ) { return - 1 ; } int ans = stk [-- i ] + add [ i ]; if ( i > 0 ) { add [ i - 1 ] += add [ i ]; } add [ i ] = 0 ; return ans ; } public void increment ( int k , int val ) { if ( i > 0 ) { add [ Math . min ( i , k ) - 1 ] += val ; } } } /** * Your CustomStack object will be instantiated and called as such: * CustomStack obj = new CustomStack(maxSize); * obj.push(x); * int param_2 = obj.pop(); * obj.increment(k,val); */
```

### CPP

```cpp
class CustomStack { public: CustomStack ( int maxSize ) { stk . resize ( maxSize ); add . resize ( maxSize ); i = 0 ; } void push ( int x ) { if ( i < stk . size ()) { stk [ i ++ ] = x ; } } int pop () { if ( i <= 0 ) { return - 1 ; } int ans = stk [ -- i ] + add [ i ]; if ( i > 0 ) { add [ i - 1 ] += add [ i ]; } add [ i ] = 0 ; return ans ; } void increment ( int k , int val ) { if ( i > 0 ) { add [ min ( k , i ) - 1 ] += val ; } } private: vector < int > stk ; vector < int > add ; int i ; }; /** * Your CustomStack object will be instantiated and called as such: * CustomStack* obj = new CustomStack(maxSize); * obj->push(x); * int param_2 = obj->pop(); * obj->increment(k,val); */
```

### Python

```python
class CustomStack : def __init__ ( self , maxSize : int ): self . stack = [] self . max_size = maxSize self . inc = [] def push ( self , x : int ) -> None : if len ( self . stack ) < self . max_size : self . stack . append ( x ) self . inc . append ( 0 ) # 0 because no range operation # not append(inc[-1]), since it will be updated on pop() def pop ( self ) -> int : if not self . stack : return - 1 if len ( self . inc ) > 1 : self . inc [ - 2 ] += self . inc [ - 1 ] return self . inc . pop () + self . stack . pop () def increment ( self , k : int , val : int ) -> None : if self . inc : self . inc [ min ( k , len ( self . inc )) - 1 ] += val # Your CustomStack object will be instantiated and called as such: # obj = CustomStack(maxSize) # obj.push(x) # param_2 = obj.pop() # obj.increment(k,val) ############### class CustomStack : def __init__ ( self , maxSize : int ): self . stk = [ 0 ] * maxSize self . add = [ 0 ] * maxSize self . i = 0 def push ( self , x : int ) -> None : if self . i < len ( self . stk ): self . stk [ self . i ] = x self . i += 1 def pop ( self ) -> int : if self . i <= 0 : return - 1 self . i -= 1 ans = self . stk [ self . i ] + self . add [ self . i ] if self . i > 0 : self . add [ self . i - 1 ] += self . add [ self . i ] self . add [ self . i ] = 0 return ans def increment ( self , k : int , val : int ) -> None : i = min ( k , self . i ) - 1 if i >= 0 : self . add [ i ] += val # Your CustomStack object will be instantiated and called as such: # obj = CustomStack(maxSize) # obj.push(x) # param_2 = obj.pop() # obj.increment(k,val)
```