LeetCode Entry

1381. Design a Stack With Increment Operation

30.09.2024 medium 2024 kotlin rust

Stack with range increment operation

1381. Design a Stack With Increment Operation medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/751

Problem TLDR

Stack with range increment operation #medium #design

Intuition

The naive solution with a single array and O(n) increment operation is accepted.

The clever one is to maintain a second array for increments and compute them only for the pop operation, shrinking it by one position. Only the last increment matters for the stack top.

Approach

• let’s implement both solutions

Complexity

• Time complexity: \(O(n)\) for n calls

• Space complexity: \(O(n)\)

Code

class CustomStack(maxSize: Int) {
    val arr = IntArray(maxSize); var head = 0
    fun push(x: Int) {
        if (head < arr.size) arr[head++] = x }
    fun pop() = if (head == 0) -1 else arr[--head]
    fun increment(k: Int, v: Int) {
        for (i in 0..<min(k, head)) arr[i] += v }
}

class CustomStack(maxSize: Int) {
    val arr = IntArray(maxSize); var size = 0
    val inc = IntArray(maxSize + 1)
    fun push(x: Int) { if (size < arr.size) arr[size++] = x }
    fun pop() = if (size < 1) -1 else inc[size] + arr[size - 1].also {
        inc[size - 1] += inc[size]; inc[size--] = 0
    }
    fun increment(k: Int, v: Int) {  inc[min(k, size)] += v }
}

struct CustomStack(Vec<i32>, Vec<i32>, usize);
impl CustomStack {
    fn new(maxSize: i32) -> Self {
        Self(vec![0; maxSize as usize], vec![0; maxSize as usize + 1], 0) }
    fn push(&mut self, x: i32) {
        if self.2 < self.0.len() { self.0[self.2] = x; self.2 += 1 } }
    fn pop(&mut self) -> i32 { if self.2 < 1 { -1 } else {
        let res = self.1[self.2] + self.0[self.2 -1];
        self.1[self.2 - 1] += self.1[self.2];
        self.1[self.2] = 0; self.2 -= 1;
        res }}
    fn increment(&mut self, k: i32, val: i32) {
        self.1[self.2.min(k as usize)] += val }
}

class CustomStack {
public:
    vector<int> arr, inc; int size;
    CustomStack(int maxSize): arr(maxSize), inc(maxSize + 1), size(0){}
    void push(int x) { if (size < arr.size()) arr[size++] = x; }
    int pop() {
        if (size < 1) return -1;
        int res = inc[size] + arr[size - 1];
        inc[size - 1] += inc[size]; inc[size--] = 0;
        return res;
    }
    void increment(int k, int val) { inc[min(k, size)] += val; }
};