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 <= 10000 <= val <= 1001000 calls will be made to each method of increment, push and pop each separately.Problem Overview: Design a custom stack that supports push, pop, and increment(k, val). The increment operation adds val to the bottom k elements of the stack without exceeding the stack's maximum capacity.
Approach 1: Direct Array-Based Implementation (Push/Pop O(1), Increment O(k))
The simplest solution stores elements in a fixed-size array representing the stack. push appends to the end if capacity allows, and pop removes the last element. For increment(k, val), iterate from index 0 to min(k, size) - 1 and add val to each element. This approach uses basic array operations and mirrors how a standard stack behaves internally. Time complexity is O(1) for push/pop and O(k) for increment, with O(n) space for the stack.
Approach 2: Optimized Increment Using Lazy Propagation (All Operations O(1))
The bottleneck is repeatedly updating up to k elements. Instead, maintain a second array inc[] where inc[i] stores pending increments for the stack prefix ending at index i. When increment(k, val) is called, add val to inc[min(k, size) - 1] instead of updating each element. During pop, propagate the pending increment down to the next index before removing the element. This technique behaves like lazy propagation used in advanced design problems. Every operation—push, pop, and increment—runs in O(1) time with O(n) space.
Recommended for interviews: Start with the direct array approach to show the straightforward stack simulation. Then optimize by avoiding repeated updates with the lazy increment array. Interviewers usually expect the O(1) lazy propagation solution because it demonstrates strong data structure design and the ability to optimize repeated operations.
This approach uses a direct array implementation to handle all operations. A list or array is used as the underlying data structure for the stack, and operations are directly performed on the stack as specified. This results in a direct and straightforward implementation, where increment operations iterate over the bottom k elements to increment them by the given value.
The CustomStack class keeps a list stack which is the container for stack elements. maxSize is the maximum capacity for the stack. In the push method, the element is added if the stack has not exceeded the set maxSize. The pop method removes and returns the top element or -1 if the stack is empty. In the increment method, the bottom k elements are incremented by iterating through each and adding the given val.
Python
JavaScript
Time Complexity: O(k) for the increment operation, O(1) for the push and pop operations.
Space Complexity: O(n) where n is the max size of the stack.
This approach uses an auxiliary array to optimize the increment operation by storing lazy increments and applying them during the pop operation. This lazy approach ensures that increments do not have to iterate over the stack directly, thus reducing potential redundant operations.
In this C++ implementation, a CustomStack includes two vectors: stack for the elements and increment for storing lazy increments. Increments are applied when popping an element, allowing lazy updates using increment[idx] to distribute the incremented value. The increment array propagates the increments when an element is popped.
Time Complexity: O(1) for push and pop; O(1) amortized for increment.
Space Complexity: O(n) where n is the max size of the stack.
We can use an array stk to simulate the stack, and an integer i to represent the position of the next element to be pushed into the stack. In addition, we need another array add to record the cumulative increment value at each position.
When calling push(x), if i < maxSize, we put x into stk[i] and increment i by one.
When calling pop(), if i leq 0, it means the stack is empty, so we return -1. Otherwise, we decrement i by one, and the answer is stk[i] + add[i]. Then we add add[i] to add[i - 1], and set add[i] to zero. Finally, we return the answer.
When calling increment(k, val), if i > 0, we add val to add[min(i, k) - 1].
The time complexity is O(1), and the space complexity is O(n). Where n is the maximum capacity of the stack.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Array-Based Implementation | Time Complexity: |
| Optimized Increment Using Lazy Propagation | Time Complexity: |
| Array Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Array-Based Implementation | Push/Pop: O(1), Increment: O(k) | O(n) | Good for understanding the stack behavior and simple implementations |
| Lazy Propagation Increment Optimization | O(1) per operation | O(n) | Best for interviews and large operation counts where repeated increments must be efficient |
Design a Stack With Increment Operation | Leetcode 1381 • Pepcoding • 6,395 views views
Watch 9 more video solutions →Practice Design a Stack With Increment Operation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor