Increment stack · Coding Gym

Solutions

A straightforward solution uses a dynamic array (such as a list or vector) to represent the stack. Pushing corresponds to appending an element, and popping removes and returns the last element. To perform an increment, we iterate over the first k elements and add the given value to each one directly.

While the problem can be solved without extra abstraction, it also provides a good opportunity to encapsulate the logic in a class that cleanly organizes the three core operations. This not only improves readability but also lays the groundwork for potential optimizations later. Here’s a sample in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class IncrementStack {
public:
    void push(int x)
    {
        m_stack.push_back(x);
    }
    
    int pop()
    {
        const auto top = m_stack.back();
        m_stack.pop_back();
        return top;
    }
    
    void increment(int k, int val)
    {
        transform(begin(m_stack), next(begin(m_stack), k), begin(m_stack), [=](auto x){
            return x + val;
        });
    }
private:
    vector<int> m_stack;
};

int main()
{
    int n, cmd, arg1, arg2; cin >> n;
    IncrementStack stack;
    while (n--)
    {
        cin >> cmd;
        switch (cmd)
        {
            case 1:
                cin >> arg1;
                stack.push(arg1);
                break;
            case 2:
                cout << stack.pop() << "\n";
                break;
            case 3:
                cin >> arg1 >> arg2;
                stack.increment(arg1, arg2);
                break;
        }
    }
}

The complexity of this solution follows:

push takes amortized constant time
pop takes constant time
increment takes \(O(k)\) time, since it updates each of the first k elements individually.

The space complexity is \(O(S)\), where S is the maximum size of the stack at any point, thus we can assume it’s at most N.

An important aspect to consider is that the overall time complexity depends heavily on both the number of the increment operations. In the worst case, if many increment commands target large portions of the stack (for example, up to its full size), the total runtime can approach \(O(N^2)\), where \(N\) is the total number of operations.

To illustrate, imagine first pushing \(N/2\) elements onto the stack, followed by \(N/2\) increment operations each affecting \(N/2\) elements. Each increment then requires iterating over roughly \(N/2\) elements, resulting in a total of about \( (N/2) \cdot (N/2) = O(N^2) \) work. This clearly demonstrates the quadratic growth in runtime under such conditions.

Although this is not a critical issue in the current challenge, an interesting alternative solution is based on lazy propagation: delaying updates until absolutely necessary. Instead of immediately updating all affected elements during an increment, we store the increment values separately and apply them only when needed. This approach is especially useful when working with ranges of elements without requiring immediate updates.

The idea is to trade some extra space for efficiency by maintaining a separate increments array alongside the stack. Each time an element is pushed, a corresponding increment value of 0 is appended to this increments array. When an increment operation affects the first k elements, we add the increment value val to the k-th position in the increments array.

The interesting part happens during pop: when the top element is removed, its corresponding increment value is also retrieved and removed from the increments array. If this increment is non-zero, it is propagated to the previous element’s increment value, ensuring that increments accumulate correctly over time without needing to update the entire range eagerly.

Suppose we have this stack (top is the rightmost):

If we increment the oldest two elements by 2, we update the increments array at position 1 (0-indexed), initially all zeros, like this:

1

0 2 0 0

Then, we increment the very first element by 100:

1

100 2 0 0

The stack remains:

After popping twice (removing 4 and 3), the stack becomes:

When popping the element 2, we combine its increment value 2 with any propagated increments, resulting in an effective increment of 4. This increment 2 is then propagated leftward, updating the increments array to:

1

102

Finally, when popping 1, its increment becomes 1 + 102 = 103, reflecting all previous accumulated increments correctly.

Having introduced a class shows its convenience here, as we only present an updated IncrementStack:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class IncrementStack {
public:
    
    void push(int x)
    {
        m_stack.push_back(x);
        m_increments.push_back(0);
    }
    
    int pop()
    {
        auto top = m_stack.back();
        const auto increment = m_increments.back();
        top += increment;
        m_stack.pop_back();
        m_increments.pop_back();
        if (increment && !m_increments.empty())
        {
            m_increments.back() += increment;
        }
        return top;
    }
    
    void increment(int k, int val)
    {
        m_increments[min(m_increments.size(), size_t(k))-1] += val;
    }
private:
    vector<int> m_stack;
    vector<int> m_increments;
};

To better appreciate the effect of this optimization, compare test case 8 using both the lazy propagation approach and the naive method. You will notice a significant difference in performance and efficiency.

The time complexity of all operations is now constant (push remains amortized), while the space complexity stays linear (although we double the size of the increments array, it remains asymptotically linear).