1381. Design a Stack With Increment Operation - Detailed Explanation

Problem Statement

You need to design a custom stack that supports the following operations:

1. CustomStack(int maxSize):
   Initializes the object with maxSize which is the maximum number of elements in the stack.

2. void push(int x):
   Adds x to the top of the stack if the stack hasn’t reached the maximum size.

3. int pop():
   Pops and returns the top element of the stack. If the stack is empty, returns -1.

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

Example:

Input:
["CustomStack","push","push","pop","push","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5],[100,2],[2,100],[],[],[],[]]

Output:
[null,null,null,2,null,null,null,null,null,null,103,202,201,-1]

Explanation:

1. CustomStack(3) → create a stack of maxSize 3.
2. push(1) → stack becomes [1].
3. push(2) → stack becomes [1, 2].
4. pop() → returns 2, stack becomes [1].
5. push(2) → stack becomes [1, 2].
6. push(3) → stack becomes [1, 2, 3].
7. push(4) → stack is full, so no change.
8. push(5) → still full.
9. increment(100, 2) → add 2 to all bottom 100 elements; effectively, stack becomes [3, 4, 5].
10. increment(2, 100) → add 100 to the bottom 2 elements; stack becomes [103, 104, 5].
11. pop() → returns 5 (top element plus any increment), but because of our lazy propagation (explained below), the effective value becomes 5 + some carried increment; see walkthrough.
12. And so on.

Key Insights and Hints

• Lazy Increment Technique:
  Directly updating the bottom ( k ) elements for each increment operation is costly (O(k) per call). Instead, we can use an auxiliary array to store "pending" increments that should be applied when an element is popped.

• How It Works:

  • Maintain two arrays:
    • stack[]: Stores the actual values pushed.
    • inc[]: An array (of size maxSize) that tracks the extra increment value that should be added to the element at that index.
  • For increment(k, val), instead of updating the bottom ( k ) elements immediately, add val to inc[min(k, stack.size) - 1].
  • When performing a pop(), add the pending increment at that index to the popped value, then propagate the increment to the next element in the stack (i.e. inc[i-1] += inc[i]).

• Avoiding Extra Work:
  This lazy propagation approach ensures that each increment operation runs in O(1) time, and pop() operations remain O(1) as well.

Step-by-Step Walkthrough

1. Initialization:

   • The constructor creates an empty stack and an auxiliary inc array (of the same maximum size) initialized with zeros.

2. Push Operation:

   • Add an element to the stack only if the current size is less than maxSize.

3. Pop Operation:

   • Check if the stack is empty; if yes, return -1.
   • Let i be the current index (i.e. stack.size - 1).
   • Before popping, propagate the inc value at index i to index i - 1 (if i > 0).
   • The result to return is stack[i] + inc[i].
   • Reset inc[i] to 0 and remove the element from the stack.

4. Increment Operation:

   • Determine the index to update: ( i = \min(k, \text{stack.size}) - 1 ).
   • If i is valid (i.e. ( \geq 0 )), add val to inc[i].

Code Implementations

Python Code