1381. Design a Stack With Increment Operation LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1381. Design a Stack With Increment Operation LeetCode Solution with the best time and space complexity. The solution to Design a Stack With Increment Operation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Design a Stack With Increment Operation solution in C++
Design a Stack With Increment Operation solution in Java
Design a Stack With Increment Operation solution in Python
Additional Resources

1381. Design a Stack With Increment Operation LeetCode Solution image

Problem Statement of Design a Stack With Increment Operation

Design a stack that supports increment operations on its elements.
Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
int pop() Pops and returns the top of the 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, 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 stk = new CustomStack(3); // Stack is Empty []
stk.push(1); // stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.pop(); // return 2 –> Return top of the stack 2, stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.push(3); // stack becomes [1, 2, 3]
stk.push(4); // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100); // stack becomes [101, 102, 103]
stk.increment(2, 100); // stack becomes [201, 202, 103]
stk.pop(); // return 103 –> Return top of the stack 103, stack becomes [201, 202]
stk.pop(); // return 202 –> Return top of the stack 202, stack becomes [201]
stk.pop(); // return 201 –> Return top of the stack 201, stack becomes []
stk.pop(); // return -1 –> Stack is empty return -1.

Constraints:

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

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(|\texttt{push()}|)

1381. Design a Stack With Increment Operation LeetCode Solution in C++

class CustomStack {
 public:
  CustomStack(int maxSize) : maxSize(maxSize) {}

  void push(int x) {
    if (stack.size() == maxSize)
      return;
    stack.push(x);
    pendingIncrements.push_back(0);
  }

  int pop() {
    if (stack.empty())
      return -1;
    const int i = stack.size() - 1;
    if (i > 0)
      pendingIncrements[i - 1] += pendingIncrements[i];
    const int val = stack.top() + pendingIncrements[i];
    stack.pop();
    pendingIncrements.pop_back();
    return val;
  }

  void increment(int k, int val) {
    if (stack.empty())
      return;
    const int i = min(k - 1, static_cast<int>(stack.size()) - 1);
    pendingIncrements[i] += val;
  }

 private:
  const int maxSize;
  stack<int> stack;
  // pendingIncrements[i] := the pending increment for stack[0..i].
  vector<int> pendingIncrements;
};
/* code provided by PROGIEZ */

1381. Design a Stack With Increment Operation LeetCode Solution in Java

class CustomStack {
  public CustomStack(int maxSize) {
    this.maxSize = maxSize;
  }

  public void push(int x) {
    if (stack.size() == maxSize)
      return;
    stack.push(x);
    pendingIncrements.add(0);
  }

  public int pop() {
    if (stack.isEmpty())
      return -1;
    final int i = stack.size() - 1;
    final int pendingIncrement = pendingIncrements.get(i);
    pendingIncrements.remove(i);
    if (i > 0)
      pendingIncrements.set(i - 1, pendingIncrements.get(i - 1) + pendingIncrement);
    return stack.pop() + pendingIncrement;
  }

  public void increment(int k, int val) {
    if (stack.isEmpty())
      return;
    final int i = Math.min(k - 1, stack.size() - 1);
    pendingIncrements.set(i, pendingIncrements.get(i) + val);
  }

  private int maxSize;
  private Deque<Integer> stack = new ArrayDeque<>();
  // pendingIncrements[i] := the pending increment for stack[0..i].
  private List<Integer> pendingIncrements = new ArrayList<>();
}
// code provided by PROGIEZ

1381. Design a Stack With Increment Operation LeetCode Solution in Python

class CustomStack:
  def __init__(self, maxSize: int):
    self.maxSize = maxSize
    self.stack = []
    # pendingIncrements[i] := the pending increment for stack[0..i].
    self.pendingIncrements = []

  def push(self, x: int) -> None:
    if len(self.stack) == self.maxSize:
      return
    self.stack.append(x)
    self.pendingIncrements.append(0)

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

  def increment(self, k: int, val: int) -> None:
    if not self.stack:
      return
    i = min(k - 1, len(self.stack) - 1)
    self.pendingIncrements[i] += val
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents