Skip to main content
Talentd

Build an Array With Stack Operations - Solution & Explanation

MediumArrayStackSimulation19 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

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 <= 100
  • 1 <= n <= 100
  • 1 <= target[i] <= n
  • target is 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.

Approach 1: Simulate Stack Operations with Two Pointers

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored.

Try this approach in the editor →

Approach 2: Direct Simulation by Iteration and Skipping

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n), Space complexity: O(m), where m is the number of operations.

Try this approach in the editor →

Approach 3: Simulation

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:

  • If cur < x, we add Push and Pop to the answer alternately until cur = x;
  • Then we add Push to the answer, representing reading the number x;
  • After that, we increment 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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Stack Operations with Two PointersO(n)O(1)Best general approach; mirrors the stack process described in the problem
Direct Simulation by Iteration and SkippingO(n)O(1)Cleaner implementation when iterating directly through target values

Video Solution

Build an Array With Stack Operations | Dry Run | Clean | Leetcode - 1441 • codestorywithMIK • 8,144 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Build an Array With Stack Operations easy or hard?
LeetCode classifies this problem as Medium, but many candidates find it closer to an easy simulation once the push–pop pattern is clear. The main challenge is recognizing that every skipped number requires a Push followed by a Pop.
Build an Array With Stack Operations Python/Java solution
In Python or Java, maintain a pointer for the target array and iterate numbers from 1 upward. For each number, append "Push" to the result. If the number is not equal to the current target value, immediately append "Pop". Continue until all target elements are processed. The implementation runs in O(n) time.
How to solve Build an Array With Stack Operations in O(n)?
Use a simulation strategy. Track the current stream value starting at 1 and compare it with the next value in the target array. If the numbers differ, append Push and Pop to discard the value; if they match, append Push and move to the next target element. Stop once the entire target array is constructed.
What is the best approach for Build an Array With Stack Operations?
The most common solution is a simulation using stack operations. Iterate numbers from 1 upward and compare them with the current target element. If they match, perform a Push; otherwise perform Push followed by Pop. This approach runs in O(n) time and O(1) extra space and closely follows the problem constraints.
Is Build an Array With Stack Operations asked at Google/Amazon/Meta?
Problems involving stack simulation and array construction appear frequently in technical interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of simulating operations with controlled input streams is commonly tested.
What data structure is used in Build an Array With Stack Operations?
The core concept is a stack. The operations Push and Pop represent stack behavior, although many implementations simply record the operations without maintaining an actual stack structure because the resulting sequence is predetermined by the target array.
What is the time complexity of Build an Array With Stack Operations?
The time complexity is O(n), where n is the largest number processed (typically target[target.length-1]). Each number from 1 up to that value is handled once, generating either a Push or a Push+Pop pair. Space complexity is O(1) excluding the output list of operations.

Ready to solve this problem?

Practice Build an Array With Stack Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Collect Elements