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.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.
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.
Java
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.
| Approach | Complexity |
|---|---|
| Direct Array-Based Implementation | Time Complexity: |
| Optimized Increment Using Lazy Propagation | Time Complexity: |
LeetCode 1381 - Design a Stack with Increment Operation (99.6% for speed!) • Light Of Truth • 1,282 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