#1381

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Design a Stack With Increment Operation

Implement a stack that supports push, pop, and targeted increment operations efficiently using array-based state management.

array stack design

Problem Statement

Design a stack that supports standard push and pop operations along with a specialized increment operation for the bottom elements. Implement the CustomStack class to manage this behavior while respecting a maximum size.

The CustomStack class should allow pushing elements onto the stack, popping the top element, and incrementing the bottom k elements by a given value efficiently, ensuring state consistency and avoiding overflow beyond the maximum stack size.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.

Solution Approach

Array-based Stack Representation

Use a fixed-size array to represent the stack. Maintain a pointer or size counter to track the current top. Push adds to the current index if within maxSize, pop returns and decrements the top, ensuring O(1) operations.

Lazy Increment Tracking

Instead of updating each element individually on increment, maintain a separate array to track pending increments for each stack level. Apply the increment lazily when elements are popped, which optimizes the increment operation to O(1) per call.

Edge Case Handling

Ensure that push does not exceed maxSize, pop returns -1 if the stack is empty, and increment applies only to the existing bottom elements up to k. This prevents errors and maintains correct stack state throughout operations.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(\text{maxSize})

Push and pop operations are O(1) because they only modify the top pointer and array. Increment is O(1) per call using lazy propagation, and space complexity is O(maxSize) for the stack and increment arrays.

What Interviewers Usually Probe

Checking if you optimize increment to avoid O(n) per operation.
Expecting proper handling of maxSize and empty stack cases.
Looking for clear separation of array state and increment tracking to ensure correctness.

Common Pitfalls or Variants

Common pitfalls

Applying increment directly on all k elements causes O(n) time per increment.
Forgetting to check stack size before push, causing overflow.
Returning wrong value on pop when stack is empty instead of -1.

Follow-up variants

Implement the stack without using extra increment array but with higher increment time complexity.
Allow decrement operations for the bottom k elements instead of increment.
Support dynamic resizing of the stack beyond a fixed maxSize while keeping increment efficient.

FAQ

What is the main idea behind this stack problem?

The problem focuses on managing a stack with push, pop, and bottom-element increment operations efficiently using array-based state management.

How can increment be optimized in this problem?

By tracking pending increments in a separate array and applying them lazily on pop, each increment operation can be done in O(1) time.

What happens if I pop from an empty stack?

You should return -1 whenever pop is called on an empty stack, maintaining consistency with the problem's requirements.

How does maxSize affect push operations?

Push operations must check the current stack size and only add elements if the stack has not reached maxSize to avoid overflow.

Does this problem follow a common pattern?

Yes, it follows a stack-based state management pattern where auxiliary structures track extra state like increments for efficiency.

terminal

Solution

Solution 1: Array Simulation

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class CustomStack:
    def __init__(self, maxSize: int):
        self.stk = [0] * maxSize
        self.add = [0] * maxSize
        self.i = 0

    def push(self, x: int) -> None:
        if self.i < len(self.stk):
            self.stk[self.i] = x
            self.i += 1

    def pop(self) -> int:
        if self.i <= 0:
            return -1
        self.i -= 1
        ans = self.stk[self.i] + self.add[self.i]
        if self.i > 0:
            self.add[self.i - 1] += self.add[self.i]
        self.add[self.i] = 0
        return ans

    def increment(self, k: int, val: int) -> None:
        i = min(k, self.i) - 1
        if i >= 0:
            self.add[i] += val


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

Continue Practicing

#1472 design browser history #1357 apply discount every n orders #1352 product of the last k numbers