Design a Stack With Increment Operation — Problem & Solution
Design a Stack With Increment Operation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Design a Stack With Increment Operation is a medium coding problem on arrays and stack, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Stack
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Design a stack with a capacity and one extra operation that adds to its bottom elements.
Write the class CustomStack:
CustomStack(int maxSize)creates an empty stack that can hold at mostmaxSizeelements.void push(int x)putsxon top of the stack, unless the stack already holdsmaxSizeelements, in which case it does nothing.int pop()removes the top element and returns it, or returns-1if the stack is empty.void increment(int k, int value)addsvalueto each of the bottomkelements. If the stack holds fewer thankelements, it addsvalueto all of them.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
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: The stack fills to [1,2,3] (bottom first) and the push of 4 is ignored. increment(5,100) touches all three: [101,102,103]; increment(2,100) touches the bottom two: [201,202,103]. The pops then return 103, 202, 201, and -1 once it is empty.
Example 2
Input: ["CustomStack","pop","push","increment","pop"]
[[1],[],[7],[4,3],[]]
Output: [null,-1,null,null,10]
Explanation: Popping an empty stack gives -1. increment(4,3) reaches beyond the single element and simply adds 3 to it.
Constraints
1 <= maxSize, x, k <= 10000 <= value <= 100At most 1000 calls are made to each of push, pop and increment
Hints for Design a Stack With Increment Operation
Hint 1
An array holds the stack. Adding
valueto the bottomkelements one by one is O(k) per increment — can you defer the work?Hint 2
Only
popever reads an element. Record the increment at the topmost element it reaches, indexmin(k, size) - 1, in a parallel arrayinc.Hint 3
When popping index
i, returnstack[i] + inc[i]and passinc[i]down toinc[i - 1]: everything belowireceived that increment too.
How to solve Design a Stack With Increment Operation
Lazy increments: store each increment once, at the highest index it covers, and let it trickle down one element at a time as the stack is popped.
Approach
- Keep the stack in an array
stand a parallel arrayincof pending additions, both empty. push(x): if there is room, appendxtostand0toinc.increment(k, value): if the stack is not empty, addvaluetoinc[min(k, size) - 1].pop(): if empty return -1. Otherwise for the top indexi, the answer isst[i] + inc[i]; ifi > 0addinc[i]toinc[i - 1]; remove both entries and return the answer.
Why it works
Invariant: the true value of element j is st[j] plus the sum of inc[i] over all i >= j. An increment of the bottom m elements adds to exactly the elements j <= m - 1, which is what putting it at inc[m - 1] does. Popping the top i reads its true value st[i] + inc[i] (nothing is above it), and moving inc[i] to inc[i - 1] keeps the sum for every element below unchanged.
Complexity
- Time —
O(1) per call - Space —
O(maxSize)
Pitfalls
- Forgetting to pass
inc[i]down on pop loses the increment for the elements underneath. incrementon an empty stack must do nothing —min(k, 0) - 1is -1.- A push onto a full stack is ignored silently; it must not overwrite the top.
Reference solution
Python
class CustomStack:
def __init__(self, maxSize: int):
self.max = maxSize
self.st = []
self.inc = [] # inc[i] is owed to st[i] and everything below it
def push(self, x: int) -> None:
if len(self.st) < self.max:
self.st.append(x)
self.inc.append(0)
def pop(self) -> int:
if not self.st:
return -1
add = self.inc.pop()
if self.inc:
self.inc[-1] += add # pass the increment down
return self.st.pop() + add
def increment(self, k: int, value: int) -> None:
i = min(k, len(self.st)) - 1
if i >= 0:
self.inc[i] += valueJava
class CustomStack {
private int[] st, inc; // inc[i] is owed to st[i] and everything below it
private int size = 0;
public CustomStack(int maxSize) {
st = new int[maxSize];
inc = new int[maxSize];
}
public void push(int x) {
if (size < st.length) { st[size] = x; inc[size] = 0; size++; }
}
public int pop() {
if (size == 0) return -1;
int i = --size;
if (i > 0) inc[i - 1] += inc[i]; // pass the increment down
return st[i] + inc[i];
}
public void increment(int k, int value) {
int i = Math.min(k, size) - 1;
if (i >= 0) inc[i] += value;
}
}C++
class CustomStack {
vector<int> st, inc; // inc[i] is owed to st[i] and everything below it
int maxSize;
public:
CustomStack(int maxSize) : maxSize(maxSize) {}
void push(int x) {
if ((int)st.size() < maxSize) { st.push_back(x); inc.push_back(0); }
}
int pop() {
if (st.empty()) return -1;
int i = st.size() - 1;
int res = st[i] + inc[i];
if (i > 0) inc[i - 1] += inc[i]; // pass the increment down
st.pop_back();
inc.pop_back();
return res;
}
void increment(int k, int value) {
int i = min(k, (int)st.size()) - 1;
if (i >= 0) inc[i] += value;
}
};JavaScript
var CustomStack = function(maxSize) {
this.max = maxSize;
this.st = [];
this.inc = []; // inc[i] is owed to st[i] and everything below it
};
CustomStack.prototype.push = function(x) {
if (this.st.length < this.max) { this.st.push(x); this.inc.push(0); }
};
CustomStack.prototype.pop = function() {
if (this.st.length === 0) return -1;
var add = this.inc.pop();
if (this.inc.length) this.inc[this.inc.length - 1] += add; // pass the increment down
return this.st.pop() + add;
};
CustomStack.prototype.increment = function(k, value) {
var i = Math.min(k, this.st.length) - 1;
if (i >= 0) this.inc[i] += value;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure