Design a Stack With Increment Operation

Medium
2066.

Design a Stack With Increment Operation

MediumArrayStackDesignAmazon

Design a Stack With Increment Operation is a medium coding problem on arrays and stack, asked in Amazon interviews.

Design a stack with a capacity and one extra operation that adds to its bottom elements.

Write the class CustomStack:

  • CustomStack(int maxSize) creates an empty stack that can hold at most maxSize elements.
  • void push(int x) puts x on top of the stack, unless the stack already holds maxSize elements, in which case it does nothing.
  • int pop() removes the top element and returns it, or returns -1 if the stack is empty.
  • void increment(int k, int value) adds value to each of the bottom k elements. If the stack holds fewer than k elements, it adds value to all of them.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

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
The stack fills to [1,2,3] (bottom first) and the push of 4 is ignored. increment(5,100) touches all three: [101,102,103]; increment(2,100) touches the bottom two: [201,202,103]. The pops then return 103, 202, 201, and -1 once it is empty.

Example 2

Input
["CustomStack","pop","push","increment","pop"] [[1],[],[7],[4,3],[]]
Output
[null,-1,null,null,10]
Explanation
Popping an empty stack gives -1. increment(4,3) reaches beyond the single element and simply adds 3 to it.

Constraints

  • 1 <= maxSize, x, k <= 1000
  • 0 <= value <= 100
  • At most 1000 calls are made to each of push, pop and increment
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} maxSize
 */
var CustomStack = function(maxSize) {
    
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function(x) {
    
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {
    
};

/**
 * @param {number} k
 * @param {number} value
 * @return {void}
 */
CustomStack.prototype.increment = function(k, value) {
    
};

Sign in to run your own test cases

Sign in

Design a Stack With Increment Operation — Problem & Solution

Design a Stack With Increment Operation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Design a Stack With Increment Operation is a medium coding problem on arrays and stack, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Stack
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Design a stack with a capacity and one extra operation that adds to its bottom elements.

Write the class CustomStack:

  • CustomStack(int maxSize) creates an empty stack that can hold at most maxSize elements.
  • void push(int x) puts x on top of the stack, unless the stack already holds maxSize elements, in which case it does nothing.
  • int pop() removes the top element and returns it, or returns -1 if the stack is empty.
  • void increment(int k, int value) adds value to each of the bottom k elements. If the stack holds fewer than k elements, it adds value to all of them.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

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: The stack fills to [1,2,3] (bottom first) and the push of 4 is ignored. increment(5,100) touches all three: [101,102,103]; increment(2,100) touches the bottom two: [201,202,103]. The pops then return 103, 202, 201, and -1 once it is empty.

Example 2

Input: ["CustomStack","pop","push","increment","pop"]
[[1],[],[7],[4,3],[]]
Output: [null,-1,null,null,10]
Explanation: Popping an empty stack gives -1. increment(4,3) reaches beyond the single element and simply adds 3 to it.

Constraints

  • 1 <= maxSize, x, k <= 1000
  • 0 <= value <= 100
  • At most 1000 calls are made to each of push, pop and increment

Hints for Design a Stack With Increment Operation

  1. Hint 1

    An array holds the stack. Adding value to the bottom k elements one by one is O(k) per increment — can you defer the work?

  2. Hint 2

    Only pop ever reads an element. Record the increment at the topmost element it reaches, index min(k, size) - 1, in a parallel array inc.

  3. Hint 3

    When popping index i, return stack[i] + inc[i] and pass inc[i] down to inc[i - 1]: everything below i received that increment too.

How to solve Design a Stack With Increment Operation

Lazy increments: store each increment once, at the highest index it covers, and let it trickle down one element at a time as the stack is popped.

Approach

  1. Keep the stack in an array st and a parallel array inc of pending additions, both empty.
  2. push(x): if there is room, append x to st and 0 to inc.
  3. increment(k, value): if the stack is not empty, add value to inc[min(k, size) - 1].
  4. pop(): if empty return -1. Otherwise for the top index i, the answer is st[i] + inc[i]; if i > 0 add inc[i] to inc[i - 1]; remove both entries and return the answer.

Why it works

Invariant: the true value of element j is st[j] plus the sum of inc[i] over all i >= j. An increment of the bottom m elements adds to exactly the elements j <= m - 1, which is what putting it at inc[m - 1] does. Popping the top i reads its true value st[i] + inc[i] (nothing is above it), and moving inc[i] to inc[i - 1] keeps the sum for every element below unchanged.

Complexity

  • Time — O(1) per call
  • Space — O(maxSize)

Pitfalls

  • Forgetting to pass inc[i] down on pop loses the increment for the elements underneath.
  • increment on an empty stack must do nothing — min(k, 0) - 1 is -1.
  • A push onto a full stack is ignored silently; it must not overwrite the top.

Reference solution

Python

class CustomStack:

    def __init__(self, maxSize: int):
        self.max = maxSize
        self.st = []
        self.inc = []  # inc[i] is owed to st[i] and everything below it

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

    def pop(self) -> int:
        if not self.st:
            return -1
        add = self.inc.pop()
        if self.inc:
            self.inc[-1] += add  # pass the increment down
        return self.st.pop() + add

    def increment(self, k: int, value: int) -> None:
        i = min(k, len(self.st)) - 1
        if i >= 0:
            self.inc[i] += value

Java

class CustomStack {
    private int[] st, inc; // inc[i] is owed to st[i] and everything below it
    private int size = 0;

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

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

    public int pop() {
        if (size == 0) return -1;
        int i = --size;
        if (i > 0) inc[i - 1] += inc[i]; // pass the increment down
        return st[i] + inc[i];
    }

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

C++

class CustomStack {
    vector<int> st, inc; // inc[i] is owed to st[i] and everything below it
    int maxSize;
public:
    CustomStack(int maxSize) : maxSize(maxSize) {}

    void push(int x) {
        if ((int)st.size() < maxSize) { st.push_back(x); inc.push_back(0); }
    }

    int pop() {
        if (st.empty()) return -1;
        int i = st.size() - 1;
        int res = st[i] + inc[i];
        if (i > 0) inc[i - 1] += inc[i]; // pass the increment down
        st.pop_back();
        inc.pop_back();
        return res;
    }

    void increment(int k, int value) {
        int i = min(k, (int)st.size()) - 1;
        if (i >= 0) inc[i] += value;
    }
};

JavaScript

var CustomStack = function(maxSize) {
    this.max = maxSize;
    this.st = [];
    this.inc = []; // inc[i] is owed to st[i] and everything below it
};

CustomStack.prototype.push = function(x) {
    if (this.st.length < this.max) { this.st.push(x); this.inc.push(0); }
};

CustomStack.prototype.pop = function() {
    if (this.st.length === 0) return -1;
    var add = this.inc.pop();
    if (this.inc.length) this.inc[this.inc.length - 1] += add; // pass the increment down
    return this.st.pop() + add;
};

CustomStack.prototype.increment = function(k, value) {
    var i = Math.min(k, this.st.length) - 1;
    if (i >= 0) this.inc[i] += value;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure