Special Stack with Increment Operation

Leetcode: https://leetcode.com/problems/design-a-stack-with-increment-operation/

Create a simple stack which takes a list of elements.
Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m, which increment the bottom n values by m.
Then print the topmost value of the stack after every operation. If the stack is empty, print “empty”

Solution:

• push and pop operations would be as usual.
• Brute Force: inc(n, m) can be achieved by simply updating the the bottom n elements with m value by accessing all the elements of the stack. Time Complexity O(q*s), where q is the number of times inc(n, m) is called and s is the size of the stack.
• Optimal solution: Keep track of the number to be added in a separate array and only access it whenever the top of the stack is accessed. Time Complexity O(1) for every inc(n, m) operation.

Code:

class CustomStack {
    int top;
    int[] a;
    int[] track;
    int MAX;
    
    public CustomStack(int maxSize) {
        MAX = maxSize;
        a = new int[maxSize];
        track = new int[maxSize];
        top = -1;
    }
    
    public void push(int x) {
        if (top >= (MAX - 1)) {
                System.out.println("Stack Overflow");
            }
            else {
                a[++top] = x;
            }
    }
    
    public int pop() {
        if (top < 0) {
                System.out.println("Stack Underflow");
                return -1;
            }
            else {
                int y = track[top];
                int x = y + a[top--];
                
                if (top >= 0) {
                    track[top] += y;
                }
                return x;
            }
    }
    
    public void increment(int k, int val) {
        if (k > top && top != -1) {
                track[top] += val;
                return;
            }
        if (k <= track.length && k>0) {
            track[k - 1] += val;
        }
    }
}