Design a Stack With Increment Operation

Time — O(1): push, pop, and increment are all constant time with the lazy increment array.
Space — O(maxSize): the value and increment arrays.

Medium

Topics

StackArrayDesign

Design a stack with a bulk-increment operation. Implement CustomStack(maxSize) and: push(x) (adds x only if the stack size is less than maxSize), pop() (removes and returns the top element, or -1 if empty), and increment(k, val) (adds val to the bottom k elements — or all of them if the stack has fewer than k).

Example 1

Input:  operations = ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"], values = [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output: [null,null,null,2,null,null,null,null,null,103,202,201,-1]

Constraints

1 <= maxSize <= 1000
1 <= x, val <= 100
0 <= k <= 1000
At most 1000 calls.

Run ⌘' · Submit ⌘⏎