Coding Interview PatternsDesign a Stack With Increment Operation
MediumCustom Data Structures

Design a Stack With Increment Operation

Explanation & Solution

Practice Problem

Description

Design a stack that supports push, pop, and an increment operation on the bottom k elements.

Implement a function that processes an array of operations and an array of arguments:

  • "CustomStack" — Initializes the stack with a max size of maxSize.
  • "push" — Pushes x onto the stack if its size is less than maxSize. Otherwise, do nothing.
  • "pop" — Pops and returns the top of the stack, or -1 if empty.
  • "increment" — Increments the bottom k elements of the stack by val. If fewer than k elements are in the stack, increment all elements.
Input:operations = ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"], args = [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
0
CustomStack
1
push
2
push
3
pop
4
push
5
push
6
push
7
increment
8
increment
9
pop
10
pop
11
pop
12
pop
Output:[null,null,null,2,null,null,null,null,null,103,202,201,-1]
0
null
1
null
2
null
3
2
4
null
5
null
6
null
7
null
8
null
9
103
10
202
11
201
12
-1

Explanation: After pushes of 1,2 we pop 2. Push 2,3,4 (4 is dropped, max=3). increment(5,100) adds 100 to all 3 elements. increment(2,100) adds 100 to bottom 2. Pop returns 3+100=103, then 2+200=202, then 1+200=201. Empty stack returns -1.

Constraints

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • At most 1000 calls to each operation

Approach

Custom Data Structures pattern

1. Use a Lazy Increment Array

  • Maintain a parallel inc array alongside the stack
  • inc[i] stores the pending increment that should be applied when element i is popped
  • This defers the actual addition until pop time — O(1) increment operation

2. Implement Push

  • If below maxSize, push x to the stack and push 0 to the inc array

3. Implement Increment

  • Instead of updating the bottom k elements individually, store the increment at index `min(k, size) - 1`
  • This single write defers updates for all affected elements

4. Implement Pop

  • The actual value of the top element is stack[top] + inc[top]
  • Before removing, propagate the increment: inc[top - 1] += inc[top]
  • This ensures elements below also receive their pending increments when they are later popped

5. Propagation Chain

  • The lazy increment cascades down through the stack on each pop
  • When an element at index i is popped, its inc[i] is added to inc[i-1]
  • This correctly applies all accumulated increments in O(1) per pop

Key Insight

  • Without the lazy approach, increment would be O(k); with it, all operations are O(1)
  • The inc array acts as a difference array — store once, apply on read
Time
O(1) for all operations
Space
O(maxSize)

Solution Code

Previous
Design Hit Counter
Next
Insert Delete GetRandom O(1)