LeetCode 1381: Design a Stack With Increment Operation Solution

Master LeetCode problem 1381 (Design a Stack With Increment Operation), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1381. Design a Stack With Increment Operation

Medium

Array Stack Design

Problem Explanation

Explanation

To design a stack with increment operation, we can implement the CustomStack class with the following functionalities:

CustomStack(int maxSize): Initializes the stack with the maximum size specified.
push(int x): Adds an element to the top of the stack if the stack has not reached its maximum size.
pop(): Removes and returns the top element of the stack or -1 if the stack is empty.
inc(int k, int val): Increments the bottom k elements of the stack by val. If there are fewer than k elements in the stack, all elements are incremented.

We can use a regular stack to store the elements and a separate array to keep track of increments for each element. When performing an increment operation, we update the increment array accordingly.

Time Complexity:

push(), pop(), inc() operations: O(1) each
Overall space complexity: O(n) where n is the maximum size of the stack

Solution Code

class CustomStack {
    int maxSize;
    Stack<Integer> stack;
    int[] inc;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new Stack<>();
        inc = new int[maxSize];
    }

    public void push(int x) {
        if (stack.size() < maxSize) {
            stack.push(x);
        }
    }

    public int pop() {
        if (stack.isEmpty()) {
            return -1;
        }
        int idx = stack.size() - 1;
        if (idx > 0) {
            inc[idx - 1] += inc[idx];
        }
        int res = stack.pop() + inc[idx];
        inc[idx] = 0;
        return res;
    }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1381 (Design a Stack With Increment Operation)?

This page provides optimized solutions for LeetCode problem 1381 (Design a Stack With Increment Operation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1381 (Design a Stack With Increment Operation)?

The time complexity for LeetCode 1381 (Design a Stack With Increment Operation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1381 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1381 in Java, C++, or Python.

Back to LeetCode Solutions