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.Problem Overview: You receive a strictly increasing target array and an integer n. Numbers from 1 to n are read sequentially, and you can only use two operations: Push (add the number to the stack) and Pop (remove the last pushed value). The goal is to output the sequence of operations that builds the exact target array.
Approach 1: Simulate Stack Operations with Two Pointers (O(n) time, O(1) space)
This method treats the process exactly like the problem statement describes. Maintain two pointers: one pointer scans numbers from 1 to n, and the other tracks the current position in the target array. For every incoming number, compare it with the current target value. If the numbers match, append Push and advance the target pointer. If they do not match, perform Push followed by Pop to discard the number. The moment the target pointer reaches the end of the array, you stop processing further numbers.
The key insight is that the numbers arrive in strictly increasing order. Any number not present in target must be temporarily pushed and immediately removed. This keeps the simulated stack consistent with the target sequence while avoiding unnecessary operations beyond the largest target value. The algorithm runs in O(n) time in the worst case (processing numbers up to target[-1]) and uses O(1) extra space besides the output. This approach naturally models a stack workflow and fits well with simulation-style problems.
Approach 2: Direct Simulation by Iteration and Skipping (O(n) time, O(1) space)
Another clean approach iterates through the target array directly instead of scanning every number independently. Track the current number that would appear in the stream (starting from 1). For each value in target, repeatedly add Push and Pop operations until the stream number reaches the target value. Once the value matches, add a single Push to keep it in the stack.
This method effectively skips ranges of numbers that are not part of the target by generating paired operations (Push, Pop) for each skipped value. Since each number between 1 and target[-1] is processed once, the time complexity remains O(n) and the extra memory usage stays O(1). The logic is simple because you always move forward and never revisit earlier values in the array.
Recommended for interviews: Interviewers expect a straightforward simulation. Both approaches run in linear time and constant auxiliary space, but the two-pointer version mirrors the stack process more explicitly. Demonstrating the push–pop simulation first shows clear understanding of the problem mechanics, while the direct iteration variant shows you can simplify the logic once the pattern becomes obvious.
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.
The C solution allocates space for operations and iterates through numbers from 1 to n, keeping track of the current position in the target array. For each number, it determines whether to only push or to push followed by pop based on whether the number is present in the target.
Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored.
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.
The C solution iterates over the numbers and compares each with the respective target, adding both "Push" and "Pop" operations when a number is not in the target to simulate skipping.
Time complexity: O(n), Space complexity: O(m), where m is the number of operations.
We define a variable cur to represent the current number to be read, initially set to cur = 1, and use an array ans to store the answer.
Next, we iterate through each number x in the array target:
cur < x, we add Push and Pop to the answer alternately until cur = x;Push to the answer, representing reading the number x;cur and continue to process the next number.After the iteration, we return the answer array.
The time complexity is O(n), where n is the length of the array target. Ignoring the space consumption of the answer array, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Simulate Stack Operations with Two Pointers | Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored. |
| Direct Simulation by Iteration and Skipping | Time complexity: O(n), Space complexity: O(m), where m is the number of operations. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Stack Operations with Two Pointers | O(n) | O(1) | Best general approach; mirrors the stack process described in the problem |
| Direct Simulation by Iteration and Skipping | O(n) | O(1) | Cleaner implementation when iterating directly through target values |
Build an Array With Stack Operations | Dry Run | Clean | Leetcode - 1441 • codestorywithMIK • 7,284 views views
Watch 9 more video solutions →Practice Build an Array With Stack Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor