> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/stack-and-queue/applications/20.-design-a-stack-with-increment-operation.md).

# 20. Design a Stack With Increment Operation

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.
```

## Solution: (Using Two Stack: O(n))

```cpp
class CustomStack
{
public:
    int ms;
    stack<int> s;

    CustomStack(int maxSize)
    {
        ms = maxSize;
    }

    void push(int x)
    {
        if (s.size() < ms)
        {
            s.push(x);
        }
        return;
    }

    int pop()
    {
        if (!s.empty())
        {
            int x = s.top();
            s.pop();
            return x;
        }

        return -1;
    }

    void increment(int k, int val)
    {

        stack<int> temp;
        while (!s.empty())
        {
            int n = s.top();
            s.pop();
            temp.push(n);
        }

        int count = 1;
        while (!temp.empty() && count <= k)
        {
            int n = temp.top();
            n += val;
            s.push(n);
            temp.pop();
            count++;
        }

        while (!temp.empty())
        {
            int n = temp.top();
            s.push(n);
            temp.pop();
        }
    }
};
```

## Solution: (Using Vector:  O(k))

```cpp
class CustomStack
{
public:
    vector<int> v;
    int ms;
    CustomStack(int maxSize)
    {
        ms = maxSize;
    }

    void push(int x)
    {
        if (v.size() < ms)
        {
            v.push_back(x);
        }

        return;
    }

    int pop()
    {

        if (v.size() > 0)
        {
            int n = v[v.size() - 1];
            v.pop_back();
            return n;
        }
        return -1;
    }

    void increment(int k, int val)
    {
        int i = 0;
        while (i < v.size() && i < k)
        {
            v[i] += val;
            i++;
        }

        return;
    }
};
```

## Solution: (Using 2 vector :  O(1))

**Approach:**\
**mainiting another vector to store increment**

```cpp
class CustomStack
{
public:
    
    vector<int> v;
    vector<int> inc;
    
    int ms;

    CustomStack(int maxSize)
    {
        ms = maxSize;
    }

    void push(int x)
    {
        if (v.size() < ms)
        {
            v.push_back(x);
            inc.push_back(0);
        }

        return;
    }

    int pop()
    {

        if (v.size() > 0)
        {
            int n = v[v.size() - 1];
            n += inc[inc.size() - 1];

            if (inc.size() > 1)
            {
                inc[inc.size() - 2] += inc[inc.size() - 1];
            }

            v.pop_back();
            inc.pop_back();
            return n;
        }
        return -1;
    }

    void increment(int k, int val)
    {
        int s = v.size();
        int idx = min(k, s) - 1;
        if (idx > -1)
        {
            inc[idx] += val;
        }
        return;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/stack-and-queue/applications/20.-design-a-stack-with-increment-operation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.