Build an Array With Stack Operations - Video Solutions
Build an Array With Stack Operations | Dry Run | Clean | Leetcode - 1441
Build an Array With Stack Operations - Video Solution
Watch 10 video solutions for Build an Array With Stack Operations, a medium level problem involving Array, Stack, Simulation. This walkthrough by codestorywithMIK has 8,144 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
- If the stack is not empty, pop the integer at the top of the stack.
- If, at any moment, the elements in the stack (from the bottom to the top) are equal to
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] <= ntargetis strictly increasing.
Approach Overview
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.
Complexity Analysis
| 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 |