Watch 10 video solutions for Design a Stack With Increment Operation, a medium level problem involving Array, Stack, Design. This walkthrough by Pepcoding has 6,395 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |