Formatted question description: https://leetcode.ca/all/1381.html

1381. Design a Stack With Increment Operation (Medium)

Design a stack which supports the following operations.

Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
int pop() Pops and returns the top of stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

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
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
At most 1000 calls will be made to each method of increment, push and pop each separately.

Related Topics:
Stack, Design

Solution - Queue

Use a double-ended queue deque. Also maintain a capacity and a size.

For the constructor, initialize deque, initialize capacity = maxSize and initialize size = 0.

For method push, if size < capacity, then add x to the end of deque and increase size by 1.

For method pop, if size > 0, then decrease size by 1, poll the first element of deque and return. Otherwise, return -1.

For method increment, set k to the minimum of k and size. For the k elements at the head of deque, poll them out, add val to each of them, and offer them back at the head of deque. Use a stack to temporally store the elements.

Solution 2 - Lazy Propogation

In this problem, we can use the concept of lazy propagation to increment the elements of the stack. Instead of incrementing the elements of the stack immediately, we can store the increment value and apply it only when the element is popped or accessed.

To implement this, we can create a separate array called lazy which stores the increment values. We will also maintain a variable called top which stores the index of the top element in the stack.

The push operation remains the same. We just need to increment top and add the element to the stack.

For the pop operation, we need to check if the stack is empty. If it is empty, we return -1. Otherwise, we get the top element of the stack, add the corresponding lazy value to it, and then decrement the lazy value of all the elements below it. Finally, we decrement top and return the element.

For the increment operation, we just need to update the lazy value of the first k elements of the stack. If k is greater than or equal to top, we update the lazy value of all the elements in the stack.

The time complexity of all operations is O(1).

class CustomStack {
    Deque<Integer> deque;
    int capacity;
    int size;

    public CustomStack(int maxSize) {
        deque = new LinkedList<Integer>();
        capacity = maxSize;
        size = 0;
    }
    
    public void push(int x) {
        if (size < capacity) {
            deque.offerLast(x);
            size++;
        }
    }
    
    public int pop() {
        if (size > 0) {
            size--;
            return deque.pollLast();
        } else
            return -1;
    }
    
    public void increment(int k, int val) {
        k = Math.min(k, size);
        Stack<Integer> tempStack = new Stack<Integer>();
        for (int i = 0; i < k; i++) {
            int num = deque.pollFirst() + val;
            tempStack.push(num);
        }
        for (int i = 0; i < k; i++)
            deque.offerFirst(tempStack.pop());
    }
}

############

class CustomStack {
    private int[] s;
    private int t;

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

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

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

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

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

// OJ: https://leetcode.com/problems/design-a-stack-with-increment-operation/
// Time:
//      CustomStack, push, pop: O(1)
//      increment: O(k)
// Space: O(N)
class CustomStack {
    int N;
    vector<int> v;
public:
    CustomStack(int maxSize): N(maxSize) {}
    void push(int x) {
        if (v.size() >= N) return;
        v.push_back(x);
    }
    int pop() {
        if (v.empty()) return -1;
        int n = v.back();
        v.pop_back();
        return n;
    }
    void increment(int k, int val) {
        k = min(k, (int)v.size());
        for (int i = 0; i < k; ++i) v[i] += val;
    }
};


// Brute force
// Time:
//      CustomStack, push, pop: O(1)
//      increment: O(k)
// Space: O(N)
class CustomStack {
    int N;
    vector<int> v;
public:
    CustomStack(int maxSize): N(maxSize) {}
    void push(int x) {
        if (v.size() >= N) return;
        v.push_back(x);
    }
    int pop() {
        if (v.empty()) return -1;
        int n = v.back();
        v.pop_back();
        return n;
    }
    void increment(int k, int val) {
        k = min(k, (int)v.size());
        for (int i = 0; i < k; ++i) v[i] += val;
    }
};

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.max_size = maxSize
        self.inc = []

    def push(self, x: int) -> None:
        if len(self.stack) < self.max_size:
            self.stack.append(x)
            self.inc.append(0)
            # 0 because no range operation
            # not append(inc[-1]), since it will be updated on pop()

    def pop(self) -> int:
        if not self.stack: return -1
        if len(self.inc) > 1:
            self.inc[-2] += self.inc[-1]
        return self.inc.pop() + self.stack.pop()

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

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

type CustomStack struct {
	s []int
	t int
}

func Constructor(maxSize int) CustomStack {
	s := make([]int, maxSize)
	return CustomStack{s, 0}
}

func (this *CustomStack) Push(x int) {
	if this.t < len(this.s) {
		this.s[this.t] = x
		this.t++
	}
}

func (this *CustomStack) Pop() int {
	if this.t == 0 {
		return -1
	}
	this.t--
	return this.s[this.t]
}

func (this *CustomStack) Increment(k int, val int) {
	for i := 0; i < k && i < this.t; i++ {
		this.s[i] += val
	}
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * obj := Constructor(maxSize);
 * obj.Push(x);
 * param_2 := obj.Pop();
 * obj.Increment(k,val);
 */

class CustomStack {
    maxSize: number;
    size: number;
    stack: Array<number>;
    constructor(maxSize: number) {
        this.maxSize = maxSize;
        this.size = 0;
        this.stack = [];
    }

    push(x: number): void {
        if (this.size >= this.maxSize) return;
        this.size++;
        this.stack.unshift(x);
    }

    pop(): number {
        if (!this.size) return -1;
        this.size--;
        return this.stack.shift();
    }

    increment(k: number, val: number): void {
        for (let i = Math.max(this.size - k, 0); i < this.size; i++) {
            this.stack[i] = this.stack[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)
 */

1381 - Design a Stack With Increment Operation

1381. Design a Stack With Increment Operation (Medium)

Solution - Queue

Solution 2 - Lazy Propogation

All Problems

All Solutions

Welcome to Subscribe On Youtube

1381. Design a Stack With Increment Operation (Medium)

Solution - Queue

Solution 2 - Lazy Propogation

All Problems

All Solutions