Skip to main content
Talentd

Design a Stack With Increment Operation - Solution & Explanation

MediumArrayStackDesign12 min readAsked at: Amazon, Microsoft, eBay +3
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: Design a custom stack that supports push, pop, and increment(k, val). The increment operation adds val to the bottom k elements of the stack without exceeding the stack's maximum capacity.

Approach 1: Direct Array-Based Implementation (Push/Pop O(1), Increment O(k))

The simplest solution stores elements in a fixed-size array representing the stack. push appends to the end if capacity allows, and pop removes the last element. For increment(k, val), iterate from index 0 to min(k, size) - 1 and add val to each element. This approach uses basic array operations and mirrors how a standard stack behaves internally. Time complexity is O(1) for push/pop and O(k) for increment, with O(n) space for the stack.

Approach 2: Optimized Increment Using Lazy Propagation (All Operations O(1))

The bottleneck is repeatedly updating up to k elements. Instead, maintain a second array inc[] where inc[i] stores pending increments for the stack prefix ending at index i. When increment(k, val) is called, add val to inc[min(k, size) - 1] instead of updating each element. During pop, propagate the pending increment down to the next index before removing the element. This technique behaves like lazy propagation used in advanced design problems. Every operation—push, pop, and increment—runs in O(1) time with O(n) space.

Recommended for interviews: Start with the direct array approach to show the straightforward stack simulation. Then optimize by avoiding repeated updates with the lazy increment array. Interviewers usually expect the O(1) lazy propagation solution because it demonstrates strong data structure design and the ability to optimize repeated operations.

Approach 1: Direct Array-Based Implementation

This approach uses a direct array implementation to handle all operations. A list or array is used as the underlying data structure for the stack, and operations are directly performed on the stack as specified. This results in a direct and straightforward implementation, where increment operations iterate over the bottom k elements to increment them by the given value.

The CustomStack class keeps a list stack which is the container for stack elements. maxSize is the maximum capacity for the stack. In the push method, the element is added if the stack has not exceeded the set maxSize. The pop method removes and returns the top element or -1 if the stack is empty. In the increment method, the bottom k elements are incremented by iterating through each and adding the given val.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(k) for the increment operation, O(1) for the push and pop operations.
Space Complexity: O(n) where n is the max size of the stack.

Try this approach in the editor →

Approach 2: Optimized Increment Using Lazy Propagation

This approach uses an auxiliary array to optimize the increment operation by storing lazy increments and applying them during the pop operation. This lazy approach ensures that increments do not have to iterate over the stack directly, thus reducing potential redundant operations.

In this C++ implementation, a CustomStack includes two vectors: stack for the elements and increment for storing lazy increments. Increments are applied when popping an element, allowing lazy updates using increment[idx] to distribute the incremented value. The increment array propagates the increments when an element is popped.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(1) for push and pop; O(1) amortized for increment.
Space Complexity: O(n) where n is the max size of the stack.

Try this approach in the editor →

Approach 3: Array Simulation

We can use an array stk to simulate the stack, and an integer i to represent the position of the next element to be pushed into the stack. In addition, we need another array add to record the cumulative increment value at each position.

When calling push(x), if i < maxSize, we put x into stk[i] and increment i by one.

When calling pop(), if i leq 0, it means the stack is empty, so we return -1. Otherwise, we decrement i by one, and the answer is stk[i] + add[i]. Then we add add[i] to add[i - 1], and set add[i] to zero. Finally, we return the answer.

When calling increment(k, val), if i > 0, we add val to add[min(i, k) - 1].

The time complexity is O(1), and the space complexity is O(n). Where n is the maximum capacity of the stack.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Array-Based Implementation

Time Complexity: O(k) for the increment operation, O(1) for the push and pop operations.
Space Complexity: O(n) where n is the max size of the stack.

Optimized Increment Using Lazy Propagation

Time Complexity: O(1) for push and pop; O(1) amortized for increment.
Space Complexity: O(n) where n is the max size of the stack.

Array Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Array-Based ImplementationPush/Pop: O(1), Increment: O(k)O(n)Good for understanding the stack behavior and simple implementations
Lazy Propagation Increment OptimizationO(1) per operationO(n)Best for interviews and large operation counts where repeated increments must be efficient

Video Solution

Design a Stack With Increment Operation | Leetcode 1381 • Pepcoding • 6,424 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design a Stack With Increment Operation easy or hard?
The problem is rated Medium because the straightforward solution is simple, but achieving optimal O(1) increments requires recognizing the lazy propagation idea. Understanding how to defer updates makes the design more challenging.
Design a Stack With Increment Operation Python/Java solution
Python solutions typically implement the direct array approach for simplicity, while Java or C++ versions often demonstrate the optimized lazy propagation technique using an additional increment array. Both versions maintain O(n) space and efficient stack operations.
How to solve Design a Stack With Increment Operation in O(n)?
The stack stores up to n elements, so total space is O(n). Achieve constant-time operations by maintaining a second array that tracks pending increments for stack prefixes. When popping, propagate the stored increment to the next index and apply it to the popped value.
What is the best approach for Design a Stack With Increment Operation?
The optimal approach uses a lazy propagation technique with an additional increment array. Instead of updating the bottom k elements directly, store pending increments and apply them when elements are popped. This keeps push, pop, and increment operations all at O(1) time with O(n) space.
Is Design a Stack With Increment Operation asked at Google/Amazon/Meta?
Stack design problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that require optimizing stack operations or designing custom data structures are common in system design and data structure interview rounds.
What data structure is used in Design a Stack With Increment Operation?
The problem primarily uses a stack implemented with an array or dynamic list. The optimized solution adds another array to store deferred increments, enabling lazy updates and constant-time operations.
What is the time complexity of Design a Stack With Increment Operation?
A basic array-based implementation runs push and pop in O(1) time but increment in O(k). The optimized lazy propagation design improves this so every operation—push, pop, and increment—runs in O(1) time with O(n) space.

Ready to solve this problem?

Practice Design a Stack With Increment Operation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays