1381. Design a Stack With Increment Operation

Description

The problem involves implementing a custom stack that supports three operations: pushing elements, popping elements, and incrementing the bottom k elements by a given value. The stack has a maximum size limit, which should be considered when adding new elements.

Intuition

The intuition behind this problem is to maintain a data structure (a stack) where elements are added and removed in a "last-in, first-out" manner. The key challenge is to handle the size constraint and efficiently update the bottom k elements during the increment operation.

Approach

1. Push Operation: If the current size of the stack is less than the allowed maximum size, the element is pushed onto the stack. Otherwise, it is ignored.
2. Pop Operation: The most recent element is removed and returned. If the stack is empty, return -1.
3. Increment Operation: For the bottom k elements, iterate through them and increase their values by the given amount. If k exceeds the stack size, increment all elements.

Complexity

• Time Complexity: - push(): O(1), as adding to the stack is constant time. - pop(): O(1), as removing from the top of the stack is constant time. - increment(): O(min(k, n)), where n is the size of the stack.
• Space Complexity: O(n), where n is the maximum size of the stack.

Code

C++

class CustomStack {
private:
    vector vec;
    int limit;

public:
    CustomStack(int maxSize) {
        limit = maxSize;
    }

    void push(int x) {
        if (vec.size() < limit) {
            vec.push_back(x);
        }
    }

    int pop() {
        if (vec.empty()) {
            return -1;
        }
        int top = vec.back();
        vec.pop_back();
        return top;
    }

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

Python

class CustomStack:

    def __init__(self, maxSize: int):
        self.vec = []
        self.limit = maxSize

    def push(self, x: int) -> None:
        if len(self.vec) < self.limit:
            self.vec.append(x)

    def pop(self) -> int:
        if not self.vec:
            return -1
        return self.vec.pop()

    def increment(self, k: int, val: int) -> None:
        for i in range(min(k, len(self.vec))):
            self.vec[i] += val

Java

class CustomStack {
    private List vec;
    private int limit;

    public CustomStack(int maxSize) {
        vec = new ArrayList<>();
        limit = maxSize;
    }

    public void push(int x) {
        if (vec.size() < limit) {
            vec.add(x);
        }
    }

    public int pop() {
        if (vec.isEmpty()) {
            return -1;
        }
        return vec.remove(vec.size() - 1);
    }

    public void increment(int k, int val) {
        for (int i = 0; i < Math.min(k, vec.size()); i++) {
            vec.set(i, vec.get(i) + val);
        }
    }
}

JavaScript

var CustomStack = function(maxSize) {
    this.vec = [];
    this.limit = maxSize;
};

CustomStack.prototype.push = function(x) {
    if (this.vec.length < this.limit) {
        this.vec.push(x);
    }
};

CustomStack.prototype.pop = function() {
    return this.vec.length === 0 ? -1 : this.vec.pop();
};

CustomStack.prototype.increment = function(k, val) {
    for (let i = 0; i < Math.min(k, this.vec.length); i++) {
        this.vec[i] += val;
    }
};

/** 
 * Your CustomStack object will be instantiated and called as such:
 * var obj = new CustomStack(maxSize)
 * obj.push(x)
 * var param_2 = obj.pop()
 * obj.increment(k,val)
 */