Design a Stack With Increment Operation

LeetCode 1381: Design a Stack With Increment Operation Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses an auxiliary array to store increment values lazily, allowing us to update the bottom $k$ elements in $O(1)$ time by propagating the increment only when elements are popped.

The problem asks us to implement a custom stack data structure with a fixed maximum size. This structure, defined in LeetCode 1381, supports three operations: adding an element to the top (push), removing the top element (pop), and a unique operation (inc) that adds a specific value to the bottom $k$ elements of the stack. The challenge in the Design a Stack With Increment Operation problem lies in handling the increment operation efficiently, especially given the constraints on stack size and operation frequency.

Brute Force Approach for Design a Stack With Increment Operation

The most straightforward way to solve this problem is to simulate the operations exactly as described using a standard dynamic array (like ArrayList in Java or vector in C++).

1. Push: Append the element to the list if the current size is less than maxSize.
2. Pop: Remove and return the last element of the list.
3. Increment: Iterate through the first k elements (or the entire list if size < k) and add val to each one.

1# Pseudo-code for Brute Force
2class CustomStack:
3    def __init__(self, maxSize):
4        self.stack = []
5        self.limit = maxSize
6
7    def push(self, x):
8        if len(self.stack) < self.limit:
9            self.stack.append(x)
10
11    def pop(self):
12        if not self.stack: return -1
13        return self.stack.pop()
14
15    def increment(self, k, val):
16        limit = min(k, len(self.stack))
17        for i in range(limit):
18            self.stack[i] += val

Time Complexity Analysis:

• push: $O(1)$
• pop: $O(1)$
• increment: $O(k)$, where $k$ is the number of elements to update.

Why it is suboptimal: While this approach passes the specific constraints of LeetCode 1381 (where $k \le 1000$), it is not scalable. If the stack size and $k$ were large (e.g., $10^5$), the increment operation would become a bottleneck, leading to Time Limit Exceeded (TLE) errors in a stricter environment. An optimal design solution should aim for $O(1)$ complexity for all operations.

Algorithm Strategy: Design Patterns

To implement the optimal solution for LeetCode 1381, we use fixed-size arrays to minimize overhead and enforce the maxSize constraint strictly.

1. Data Structures:

   • stack[]: An array to store the pushed elements.
   • inc[]: An array of the same size to store pending increment values.
   • top: An integer pointer indicating the index of the top element. Initialized to -1.

2. Push Operation:

   • Check if top + 1 < maxSize.
   • If valid, increment top.
   • Store x in stack[top].
   • Crucial: Ensure inc[top] is reset to 0 (clean state for the new element).

3. Pop Operation:

   • Check if top == -1 (empty). If so, return -1.
   • Calculate the result: stack[top] + inc[top].
   • Propagate: If top > 0, add inc[top] to inc[top - 1]. This passes the pending increment to the next element down.
   • Reset inc[top] to 0 (optional but good practice).
   • Decrement top.
   • Return the result.

4. Increment Operation:

   • Determine the target index: idx = min(top, k - 1).
   • If idx >= 0, add val to inc[idx].

Execution Flow

Let's trace the algorithm with maxSize = 3:

1. Initialize: stack=[0,0,0], inc=[0,0,0], top=-1.
2. Push 1: top becomes 0. stack[0]=1.
3. Push 2: top becomes 1. stack[1]=2.
4. Increment(2, 100): Target index is min(1, 2-1) = 1. Update inc[1] += 100.
   • State: stack=[1, 2, 0], inc=[0, 100, 0], top=1.
5. Pop:
   • Current top is 1.
   • Return value = stack[1] + inc[1] = $2 + 100 = 102$.
   • Propagate: inc[0] += inc[1] $\to$ `inc[0] = 0 + 100 = 100$.
   • Decrement top to 0.
   • Return 102.
   • State: stack=[1, 2, 0], inc=[100, 100, 0], top=0.
6. Pop:
   • Current top is 0.
   • Return value = stack[0] + inc[0] = $1 + 100 = 101$.
   • Propagate: top is 0, no index below, so stop.
   • Decrement top to -1.
   • Return 101.

Proof of Correctness

The algorithm relies on the invariant that inc[i] stores the accumulated sum of all increments that covered index i but terminated at index i (due to k limits or stack height).

When we execute inc(k, val), we effectively state that indices 0 through min(top, k-1) increase by val. By storing val only at the top of this range, we defer the operation.

During pop, the propagation step inc[top-1] += inc[top] ensures that as the "ceiling" of the stack lowers, the pending increments "fall" onto the next available element. This guarantees that every element i eventually receives the sum of all increments intended for ranges covering i, preserving the correctness of the stack values.

Pattern Reuse Notes

The design pattern used here (Lazy Propagation / Auxiliary State) is applicable to several other popular interview questions:

• LeetCode 146: LRU Cache - Uses auxiliary structures (HashMap + Doubly Linked List) to achieve $O(1)$ operations.
• LeetCode 155: Min Stack - Uses an auxiliary stack to track the minimum value at every level in $O(1)$.
• LeetCode 225: Implement Stack using Queues - Manipulates data structures to mimic LIFO behavior.
• LeetCode 232: Implement Queue using Stacks - Uses two stacks to amortize costs and achieve FIFO behavior.

Understanding how to decouple the "value" from the "operation" (like separating the stack value from its increment) is a key skill in system design and advanced algorithm problems.

Reference Implementation

C++ Solution for LeetCode 1381

1class CustomStack {
2private:
3    vector<int> stack;
4    vector<int> inc;
5    int top;
6    int maxSize;
7
8public:
9    CustomStack(int maxSize) {
10        this->maxSize = maxSize;
11        stack.resize(maxSize);
12        inc.resize(maxSize, 0);
13        top = -1;
14    }
15    
16    void push(int x) {
17        if (top < maxSize - 1) {
18            top++;
19            stack[top] = x;
20            inc[top] = 0; // Reset increment for new element
21        }
22    }
23    
24    int pop() {
25        if (top == -1) return -1;
26        
27        int result = stack[top] + inc[top];
28        
29        // Propagate increment to the element below
30        if (top > 0) {
31            inc[top - 1] += inc[top];
32        }
33        
34        // Clear current increment (optional, as push resets it)
35        inc[top] = 0;
36        top--;
37        
38        return result;
39    }
40    
41    void inc(int k, int val) {
42        if (top >= 0) {
43            // Apply increment to the specific range limit
44            int idx = min(top, k - 1);
45            inc[idx] += val;
46        }
47    }
48};

Java Solution for LeetCode 1381

1class CustomStack {
2    private int[] stack;
3    private int[] inc;
4    private int top;
5    private int maxSize;
6
7    public CustomStack(int maxSize) {
8        this.maxSize = maxSize;
9        this.stack = new int[maxSize];
10        this.inc = new int[maxSize];
11        this.top = -1;
12    }
13    
14    public void push(int x) {
15        if (top < maxSize - 1) {
16            top++;
17            stack[top] = x;
18            inc[top] = 0; // Ensure no stale increment exists
19        }
20    }
21    
22    public int pop() {
23        if (top == -1) {
24            return -1;
25        }
26        
27        int result = stack[top] + inc[top];
28        
29        // Lazy propagation: pass the increment down
30        if (top > 0) {
31            inc[top - 1] += inc[top];
32        }
33        
34        inc[top] = 0;
35        top--;
36        
37        return result;
38    }
39    
40    public void increment(int k, int val) {
41        if (top >= 0) {
42            int index = Math.min(top, k - 1);
43            inc[index] += val;
44        }
45    }
46}

Python Solution for LeetCode 1381

1class CustomStack:
2    def __init__(self, maxSize: int):
3        # Initialize stack and increment array
4        self.stack = []
5        self.inc = []
6        self.max_size = maxSize
7
8    def push(self, x: int) -> None:
9        if len(self.stack) < self.max_size:
10            self.stack.append(x)
11            self.inc.append(0)
12
13    def pop(self) -> int:
14        if not self.stack:
15            return -1
16        
17        # Current top index
18        idx = len(self.stack) - 1
19        
20        # Calculate return value
21        result = self.stack.pop() + self.inc[idx]
22        
23        # Propagate increment if elements remain
24        if idx > 0:
25            self.inc[idx - 1] += self.inc[idx]
26            
27        self.inc.pop()
28        return result
29
30    def increment(self, k: int, val: int) -> None:
31        if self.stack:
32            # Find the top-most element of the bottom k elements
33            idx = min(len(self.stack), k) - 1
34            if idx >= 0:
35                self.inc[idx] += val