MediumStackDesignArray

Design a Stack With Increment Operation

1 approach, code in all languages

Design a stack of bounded capacity that, in addition to the usual push and pop, supports a bulk increment on its oldest elements.

Implement the CustomStack class: the constructor takes maxSize and creates an empty stack that can hold at most maxSize elements. push(x) adds x to the top only if the stack has not reached maxSize, otherwise it does nothing. pop() removes and returns the top element, or returns -1 if the stack is empty. increment(k, val) adds val to the bottom k elements of the stack; if there are fewer than k elements, it adds val to all of them.

Aim for an efficient increment that does not touch every affected element on each call.

Example 1

Input: ["CustomStack","push","push","increment","pop","push","pop"] [[3],[1],[2],[5,100],[],[3],[]]

Output: [null,null,null,null,102,null,3]

Push 1 then 2. increment(5,100) adds 100 to all elements (only 2 exist), giving [101,102]. pop() returns 102. Push 3 to get [101,3]. pop() returns 3.

Example 2

Input: ["CustomStack","push","push","push","increment","increment","pop","pop","pop","pop"] [[3],[1],[2],[3],[2,100],[3,10],[],[],[],[]]

Output: [null,null,null,null,null,null,13,112,111,-1]

Stack becomes [1,2,3]. increment(2,100) adds 100 to the bottom 2 giving [101,102,3]; increment(3,10) adds 10 to all three giving [111,112,13]. The pops then return 13, 112, and 111 from the top down, and the final pop on the empty stack returns -1.

Constraints

1 <= maxSize, x, k <= 1000
0 <= val <= 100
At most 1000 calls in total will be made to push, pop, and increment

Array With Lazy Increment

Store values in an array and defer bulk increments using a parallel inc[] array applied only at pop time.

Loading animation…

Intuition

A naive increment would walk over the bottom k elements every call, which is slow when increments are frequent. Instead, record the increment lazily. Keep a parallel array inc where inc[i] carries the amount that should eventually be added to elements at indices 0 through i. An increment(k, val) only needs to bump inc[min(k, size) - 1] by val, marking that the bottom that-many elements owe an extra val. The debt is settled at pop time: when you remove the top element you add its inc value to it, and you push that same debt down one level by adding it to inc[top - 1], so the elements below still receive their share. This makes every operation constant time.

Algorithm walkthrough

1Back the stack with a values array (or list) plus a same-length inc array of pending increments, and track the current size.
2push(x): if size is below maxSize, store x at the top slot, set its inc entry to 0, and grow the size.
3pop(): if empty return -1; otherwise read the top index, take add = inc[top].
4Propagate the debt down: if top > 0, do inc[top - 1] += add so lower elements still get their increment.
5Clear inc[top], shrink the size, and return the stored value plus add.
6increment(k, val): compute limit = min(k, size); if limit > 0, do inc[limit - 1] += val to lazily mark the bottom limit elements.

Implementation

class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.stack = []
        self.inc = []

    def push(self, x: int) -> None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self) -> int:
        if not self.stack:
            return -1
        top = len(self.stack) - 1
        add = self.inc[top]
        if top > 0:
            self.inc[top - 1] += add
        self.inc.pop()
        return self.stack.pop() + add

    def increment(self, k: int, val: int) -> None:
        limit = min(k, len(self.stack))
        if limit > 0:
            self.inc[limit - 1] += val

Time

O(1)

Space

O(maxSize)

push, pop, and increment are all constant time thanks to the lazy inc array, which uses O(maxSize) extra memory.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI