Design a Stack With Increment Operation Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Google Microsoft Sprinklr
Array Design Stack tiktokViews 2977

Problem Statement

The Design a Stack With Increment Operation Leetcode Solution –  states that we need to design a stack that supports the below operations efficiently.

  • Assign the maximum capacity of the stack.
  • Perform the push operation efficiently, if the size of the stack is strictly less than the maximum capacity of the stack.
  • Perform the pop operation efficiently if the stack is non-empty and return the popped element.
  • Perform the increment operation to the first k elements of the stack.

Design a Stack With Increment Operation Leetcode Solution

Example:

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:

  • Initialize the stack with max capacity as 3.
  • push element with value 1, stack = [1].
  • push element with value 2, stack = [1,2].
  • pop the element from the stack, stack = [1]. Output: 2.
  • push element with value 2, stack = [1,2].
  • push element with value 3, stack = [1,2,3].
  • push element with value 4. Since stack reaches it’s max capacity, we can’t push another element.
  • Increment bottom 5 elements with by value 100,stack = [101,102,103].
  • Increment bottom 2 elements with by value 100,stack = [201,202,103].
  • pop the element from stack, stack = [201,202]. Output: 103.
  • pop the element from stack, stack = [201]. Output: 202.
  • pop the element from stack, stack = []. Output: 201.
  • pop the element from the stack. Since stack is empty, output: -1.

Approach

Idea:

  1. The main idea to solve this problem efficiently is to maintain an array of sizes equal to the maximum capacity of the stack.
  2. Maintain an index variable that will denote index-1 elements are already pushed into the stack, and the new element will be pushed at a position equal to the index.
  3. For the push operation, the element will be pushed into the stack when the index is less than or equal to the maximum capacity of the stack.
  4. For the pop operation, the element will be popped out only if the stack is non-empty.
  5. For the increment operation, we need to increment the first k elements of the stack with the given value. So, we’ll iterate and increment all those elements by the given value. If there are less than k elements in the stack, we need to increment all the elements of the stack.

Code

Design a Stack With Increment Operation Leetcode C++ Solution:

class CustomStack {
public:
    vector<int> st;
    int index,maxCapacity;
    CustomStack(int maxSize) {
        index = 0;
        maxCapacity = maxSize;
        st.assign(maxSize+1,0);
    }    
    void push(int x) {
        if(index!=maxCapacity){
            st[++index] = x;
        }
    }    
    int pop() {
        if(!index){
            return -1;
        }
        return st[index--];
    }    
    void increment(int k, int val) {
        for(int i=1;i<=k && i<=index;i++){
            st[i] += val;
        }
    }
};

Design a Stack With Increment Operation Leetcode Java Solution:

class CustomStack {
    int[] st;
    int index,maxCapacity;
    public CustomStack(int maxSize) {
        index = 0;
        maxCapacity = maxSize;
        st = new int[maxSize+1];      
    }
    public void push(int x) {
        if(index!=maxCapacity){
            st[++index] = x;
        }
    }
    public int pop() {
        if(index==0){
            return -1;
        }
        return st[index--];
    }
    public void increment(int k, int val) {
        for(int i=1;i<=k && i<=index;i++){
            st[i] += val;
        }
    }
}

Complexity Analysis for Design a Stack With Increment Operation Leetcode Solution

Time Complexity

The time complexity of the above code is O(maxSize) since in the worst case, k is equal to the maximum capacity of the stack.

Space Complexity

The space complexity of the above code is O(maxSize) since we’re maintaining an array of sizes equal to the maximum capacity of the stack.

Reference: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Translate »