You are given an integer array target and an integer n.
You have an empty stack with the two following operations:
"Push": pushes an integer to the top of the stack."Pop": removes the integer on the top of the stack.You also have a stream of the integers in the range [1, n].
Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:
target, do not read new integers from the stream and do not do more operations on the stack.Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.
Example 1:
Input: target = [1,3], n = 3 Output: ["Push","Push","Pop","Push"] Explanation: Initially the stack s is empty. The last element is the top of the stack. Read 1 from the stream and push it to the stack. s = [1]. Read 2 from the stream and push it to the stack. s = [1,2]. Pop the integer on the top of the stack. s = [1]. Read 3 from the stream and push it to the stack. s = [1,3].
Example 2:
Input: target = [1,2,3], n = 3 Output: ["Push","Push","Push"] Explanation: Initially the stack s is empty. The last element is the top of the stack. Read 1 from the stream and push it to the stack. s = [1]. Read 2 from the stream and push it to the stack. s = [1,2]. Read 3 from the stream and push it to the stack. s = [1,2,3].
Example 3:
Input: target = [1,2], n = 4 Output: ["Push","Push"] Explanation: Initially the stack s is empty. The last element is the top of the stack. Read 1 from the stream and push it to the stack. s = [1]. Read 2 from the stream and push it to the stack. s = [1,2]. Since the stack (from the bottom to the top) is equal to target, we stop the stack operations. The answers that read integer 3 from the stream are not accepted.
Constraints:
1 <= target.length <= 1001 <= n <= 1001 <= target[i] <= ntarget is strictly increasing.The key idea in #1441 Build an Array With Stack Operations is to simulate how a stack would build the target array using only two operations: Push and Pop. You are given a target array and a stream of numbers from 1 to n. The goal is to generate the sequence of stack operations that constructs the target while reading numbers sequentially.
A practical approach is to iterate through numbers from 1 to n while maintaining a pointer to the current element in the target array. For each number, perform a Push operation. If the number does not match the current target value, immediately perform a Pop. If it matches, move the pointer forward and keep the value in the simulated stack.
This approach works because the input stream is strictly increasing, making it easy to determine whether a value should remain in the stack or be removed. The simulation runs efficiently with linear time complexity relative to the size of the target array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack Simulation with Sequential Iteration | O(n) | O(1) auxiliary (excluding output operations) |
daose
Use these hints if you're stuck. Try solving on your own first.
Use “Push” for numbers to be kept in target array and [“Push”, “Pop”] for numbers to be discarded.
In this approach, we use two pointers: one to iterate over the stream numbers from 1 to n, and another to iterate over the target list. For each number in the range, if the number matches the current target number, we "Push" it to the stack. If it does not match, we "Push" and then "Pop". This way, we use the minimum operations to achieve the target stack.
Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored.
1using System;
2using System.Collections.Generic;
3
4class Program {
5 static List<string> BuildArray(int[] target, int n) {
6 List<string> operations = new List<string>();
7 int t = 0;
8 for (int i = 1; i <= n && t < target.Length; ++i) {
9 operations.Add("Push");
10 if (i != target[t]) {
11 operations.Add("Pop");
12 } else {
13 ++t;
14 }
}
return operations;
}
static void Main() {
int[] target = {1, 3};
int n = 3;
List<string> operations = BuildArray(target, n);
foreach (string op in operations) {
Console.WriteLine(op);
}
}
}This C# solution makes use of a List to manage the operations. It compares each number in sequence from 1 to n against the target list, adding 'Push' for each, and 'Pop' if there is no match.
This approach involves a single iteration over both the numbers from 1 to n and the target array. Whenever a non-matching number in the stream is encountered (i.e., numbers not in the target), the number is pushed and popped immediately. This results in efficient use of stack operations to match the target.
Time complexity: O(n), Space complexity: O(m), where m is the number of operations.
1using System.Collections.Generic;
class Program {
static List<string> BuildArray(int[] target, int n) {
List<string> operations = new List<string>();
int targetIndex = 0;
for (int i = 1; i <= n; ++i) {
operations.Add("Push");
if (targetIndex < target.Length && target[targetIndex] == i) {
targetIndex++;
} else {
operations.Add("Pop");
}
}
return operations;
}
static void Main() {
int[] target = {1, 3};
int n = 3;
List<string> operations = BuildArray(target, n);
foreach (string op in operations) {
Console.WriteLine(op);
}
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The target array is strictly increasing, so once all its elements are matched, additional numbers from the stream are unnecessary. Stopping early avoids extra operations and keeps the solution efficient.
Yes, similar simulation and stack-based problems appear in FAANG-style interviews. They test your ability to translate problem constraints into sequential operations and efficiently simulate data structure behavior.
A stack concept is ideal for this problem because the allowed operations are Push and Pop. In practice, you only simulate these operations using a list of strings that records the performed actions.
The optimal approach is a stack simulation strategy. Iterate through numbers from 1 to n and compare them with the current element in the target array, performing Push for each number and Pop if it is not needed.
C# uses lists to dynamically manage operations needed to simulate stack building with systematic checks and direct operations.