Design a Stack With Increment Operation

Medium Design Data Structures Stack Original on LeetCode

Design a Stack With Increment Operation is a medium design data structures problem solved with the stack pattern. The best approach, optimal (lazy increments), runs in O(1) for every operation time and O(maxSize) space. Below are 2 approaches in Java, from direct increment up.

Problem

Design a stack with a maximum size that supports push, pop and increment(k, val), which adds val to the bottom k elements (or to all elements if there are fewer than k).

Examples

Example 1

Input: CustomStack(3); push(1); push(2); pop(); push(2); push(3); push(4); increment(5, 100); increment(2, 100); pop(); pop(); pop(); pop()
Output: 2, 103, 202, 201, -1

Constraints

1 <= maxSize <= 1000; up to 1000 calls of each method.
increment(k, val) adds val to the bottom k elements (all of them if fewer).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Direct increment	`O(k) for increment, O(1) otherwise`	`O(maxSize)`
Optimal (lazy increments)	`O(1) for every operation`	`O(maxSize)`

1Direct increment

TimeO(k) for increment, O(1) otherwise

SpaceO(maxSize)

Array-backed stack; increment loops over the bottom min(k, size) elements.

increment: for i < min(k, size): a[i] += val.

Java

class CustomStack {
    private final int[] a;
    private int size;

    public CustomStack(int maxSize) { a = new int[maxSize]; }

    public void push(int x) { if (size < a.length) a[size++] = x; }

    public int pop() { return size == 0 ? -1 : a[--size]; }

    public void increment(int k, int val) {
        for (int i = 0; i < Math.min(k, size); i++) a[i] += val;
    }
}

2Optimal (lazy increments)

TimeO(1) for every operation

SpaceO(maxSize)

inc[i] holds a pending addition for elements 0..i. increment adds val to inc[min(k, size) - 1]. On pop of index i, return a[i] + inc[i], pass inc[i] down to inc[i - 1], and clear inc[i].

increment: if size > 0, inc[min(k, size) - 1] += val.
pop: i = size - 1; result = a[i] + inc[i]; if i > 0, inc[i - 1] += inc[i]; inc[i] = 0; size--.

Java

class CustomStack {
    private final int[] a, inc;
    private int size;

    public CustomStack(int maxSize) {
        a = new int[maxSize];
        inc = new int[maxSize];
    }

    public void push(int x) { if (size < a.length) a[size++] = x; }

    public int pop() {
        if (size == 0) return -1;
        int i = --size;
        int result = a[i] + inc[i];
        if (i > 0) inc[i - 1] += inc[i];
        inc[i] = 0;
        return result;
    }

    public void increment(int k, int val) {
        if (size > 0) inc[Math.min(k, size) - 1] += val;
    }
}

Edge cases to test

push on a full stack is ignored
pop on an empty stack returns -1
k larger than the size

Hints

Hint 1

Instead of adding val to k elements now, record +val at index k - 1 and push the increment down only when that element is popped.

FAQ

What is the best time complexity for Design a Stack With Increment Operation?

Optimal (lazy increments) runs in O(1) for every operation time and O(maxSize) extra space.

Which pattern does Design a Stack With Increment Operation use?

It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Maximum Frequency Stack.

Is there a brute force solution for Design a Stack With Increment Operation?

Yes. Direct increment takes O(k) for increment, O(1) otherwise time and O(maxSize) space. Array-backed stack; increment loops over the bottom min(k, size) elements.

Which edge cases should I test for Design a Stack With Increment Operation?

push on a full stack is ignored; pop on an empty stack returns -1; k larger than the size.