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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(n), Space complexity: O(m), where m is the number of operations.
| 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. |
Build an Array With Stack Operations - LeetCode Weekly Contest 188 • daose • 2,640 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