Build an Array With Stack Operations — Problem & Solution
Build an Array With Stack Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Build an Array With Stack Operations is a medium coding problem on arrays, simulation and stack, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Simulation, Stack
- Asked at: Amazon, Adobe
- 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
You are given a strictly increasing array target and an integer n. A stream reads the integers 1, 2, …, n in order, and you build a stack with two operations:
"Push"— push the next integer from the stream;"Pop"— remove the top of the stack.
Return the shortest sequence of operations that leaves the stack equal to target. Stop as soon as the stack matches.
Example 1
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Read 1, then read 2 and discard it, then read 3.
Example 2
Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Example 3
Input: target = [1,2], n = 4
Output: ["Push","Push"]
Constraints
1 <= target.length <= 301 <= target[i] <= n <= 40target is strictly increasing.
Hints for Build an Array With Stack Operations
Hint 1
Walk the stream from 1 upward, keeping a pointer into
target.Hint 2
Every number that is not the next target value is pushed and immediately popped.
Hint 3
Stop the moment the last target value has been pushed — trailing operations are never needed.
How to solve Build an Array With Stack Operations
Walk the stream 1..n with a pointer into target: every value that is not the next target is pushed and popped, the target value is pushed, and stop after the last target.
Approach
- For each
wantintarget: whilevalue < want, emitPush, Popand increment; then emitPushand increment.
Why it works
The stream is consumed in order and target is increasing, so each intermediate number must be pushed and immediately removed. Stopping at the last target avoids useless trailing operations.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Iterating all the way to
nemits extra pushes after the target is complete.
Reference solution
Python
def buildArray(target, n: int):
out = []
value = 1
for want in target:
while value < want:
out.append("Push")
out.append("Pop")
value += 1
out.append("Push")
value += 1
return outJava
public static String[] buildArray(int[] target, int n) {
List<String> out = new ArrayList<>();
int value = 1;
for (int want : target) {
while (value < want) {
out.add("Push");
out.add("Pop");
value++;
}
out.add("Push");
value++;
}
return out.toArray(new String[0]);
}C++
vector<string> buildArray(vector<int>& target, int n) {
vector<string> out;
int value = 1;
for (int want : target) {
while (value < want) {
out.push_back("Push");
out.push_back("Pop");
value++;
}
out.push_back("Push");
value++;
}
return out;
}JavaScript
var buildArray = function(target, n) {
const out = [];
let value = 1;
for (let i = 0; i < target.length; i++) {
while (value < target[i]) {
out.push("Push");
out.push("Pop");
value++;
}
out.push("Push");
value++;
}
return out;
};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