Build an Array With Stack Operations solution and explanation
Google
9 more videos on this problem
Build an Array With Stack Operations | Dry Run | Clean | Leetcode - 1441codestorywithMIK · 14:00 · 8K views
Build an Array With Stack Operations - LeetCode Weekly Contest 188daose · 7:40 · 2K views
1441. Build an Array With Stack Operations || Leetcode weekly contest 188 || [ C++ SOLUTION ]code Explainer · 5:58 · 1K views
1441. Build an Array With Stack Operations || 2-PointersAryan Mittal · 9:13 · 1K views
Leetcode | 1441. Build an Array with Stack Operations | Medium | Java SolutionDeveloper Docs · 5:39 · 1K views
1441. Build an Array With Stack Operations (Leetcode Easy)Programming Live with Larry · 6:26 · 754 views
Leetcode 1441: Build Array With Stack Operations | Python Solution in Telugu | srkcodesSrk Codes · 11:23 · 369 views
1441. Build an Array With Stack Operations || LEETCODE SOLUTION || IN C++ || DS AND ALGOAbhishweta Gupta · 2:04 · 368 views
Daily Leetcode #1312: Nov 03, 2023 - 1441. Build an Array With Stack OperationsProgramming Live with Larry · 10:04 · 348 views
Solving LeetCode 1441 Build an Array With Stack OperationsCode Harmony · 5:38 · 340 views
The problem
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.
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.
def buildArray(target, n):
operations = []
t = 0
for i in range(1, n + 1):
if t == len(target):
break
operations.append('Push')
if i != target[t]:
operations.append('Pop')
else:
t += 1
return operations
# Example usage
result = buildArray([1, 3], 3)
for op in result:
print(op)import java.util.*;
public class BuildArray {
public List<String> buildArray(int[] target, int n) {
List<String> operations = new ArrayList<>();
int t = 0;
for (int i = 1; i <= n && t < target.length; ++i) {
operations.add("Push");
if (i != target[t]) {
operations.add("Pop");
} else {
++t;
}
}
return operations;
}
public static void main(String[] args) {
BuildArray ba = new BuildArray();
int[] target = {1, 3};
int n = 3;
List<String> operations = ba.buildArray(target, n);
for (String operation : operations) {
System.out.println(operation);
}
}
}#include <vector>
#include <string>
#include <iostream>
using namespace std;
vector<string> buildArray(vector<int>& target, int n) {
vector<string> operations;
int t = 0;
for (int i = 1; i <= n && t < target.size(); ++i) {
operations.push_back("Push");
if (i != target[t]) {
operations.push_back("Pop");
} else {
++t;
}
}
return operations;
}
int main() {
vector<int> target = {1, 3};
int n = 3;
vector<string> operations = buildArray(target, n);
for (const string &op : operations) {
cout << op << endl;
}
return 0;
}function buildArray(target, n) {
const operations = [];
let t = 0;
for (let i = 1; i <= n && t < target.length; i++) {
operations.push('Push');
if (i !== target[t]) {
operations.push('Pop');
} else {
t++;
}
}
return operations;
}
// Example usage
const result = buildArray([1, 3], 3);
result.forEach(op => console.log(op));#include <stdio.h>
#include <stdlib.h>
char** buildArray(int* target, int targetSize, int n, int* returnSize) {
char **operations = (char **)malloc(200 * sizeof(char*));
int t = 0, opIndex = 0;
for (int i = 1; i <= n && t < targetSize; ++i) {
operations[opIndex++] = "Push";
if (i != target[t]) {
operations[opIndex++] = "Pop";
} else {
t++;
}
}
*returnSize = opIndex;
return operations;
}
int main() {
int target[] = {1, 3};
int targetSize = 2;
int n = 3;
int returnSize;
char** operations = buildArray(target, targetSize, n, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", operations[i]);
}
free(operations);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static List<string> BuildArray(int[] target, int n) {
List<string> operations = new List<string>();
int t = 0;
for (int i = 1; i <= n && t < target.Length; ++i) {
operations.Add("Push");
if (i != target[t]) {
operations.Add("Pop");
} else {
++t;
}
}
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);
}
}
}The Python solution uses a list to collect operations and iterates over numbers from 1 to n while checking against the target array.
Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored.
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.
def buildArray(target, n):
operations = []
targetIndex = 0
for i in range(1, n + 1):
operations.append('Push')
if targetIndex < len(target) and target[targetIndex] == i:
targetIndex += 1
else:
operations.append('Pop')
return operations
# Example usage
result = buildArray([1, 3], 3)
for op in result:
print(op)import java.util.*;
public class BuildArraySimulation {
public List<String> buildArray(int[] target, int n) {
List<String> operations = new ArrayList<>();
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;
}
public static void main(String[] args) {
BuildArraySimulation ba = new BuildArraySimulation();
int[] target = {1, 3};
int n = 3;
List<String> operations = ba.buildArray(target, n);
for(String op : operations) {
System.out.println(op);
}
}
}#include <vector>
#include <string>
#include <iostream>
using namespace std;
vector<string> buildArray(vector<int>& target, int n) {
vector<string> operations;
int targetIndex = 0;
for (int i = 1; i <= n; ++i) {
operations.push_back("Push");
if (targetIndex < target.size() && target[targetIndex] == i) {
targetIndex++;
} else {
operations.push_back("Pop");
}
}
return operations;
}
int main() {
vector<int> target = {1, 3};
int n = 3;
vector<string> operations = buildArray(target, n);
for (const auto &op : operations) {
cout << op << endl;
}
return 0;
}function buildArray(target, n) {
const operations = [];
let targetIndex = 0;
for (let i = 1; i <= n; i++) {
operations.push('Push');
if (targetIndex < target.length && target[targetIndex] === i) {
targetIndex++;
} else {
operations.push('Pop');
}
}
return operations;
}
// Example usage
const result = buildArray([1, 3], 3);
result.forEach(op => console.log(op));#include <stdio.h>
#include <stdlib.h>
char** buildArray(int* target, int targetSize, int n, int* returnSize) {
char **operations = (char **)malloc(200 * sizeof(char*));
int opIndex = 0, targetIndex = 0;
for (int i = 1; i <= n; ++i) {
operations[opIndex++] = "Push";
if (targetIndex < targetSize && target[targetIndex] == i) {
targetIndex++;
} else {
operations[opIndex++] = "Pop";
}
}
*returnSize = opIndex;
return operations;
}
int main() {
int target[] = {1, 3};
int targetSize = 2;
int n = 3;
int returnSize;
char **operations = buildArray(target, targetSize, n, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", operations[i]);
}
free(operations);
return 0;
}using System;
using 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);
}
}
}Python's solution iterates using a for loop, checking if the current stream number corresponds to the next target number, adding "Push" and "Pop" as necessary.
Time complexity: O(n), Space complexity: O(m).
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 addPushandPopto the answer alternately untilcur = x; - Then we add
Pushto the answer, representing reading the numberx; - After that, we increment
curand 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).
function buildArray(target: number[], n: number): string[] {
const ans: string[] = [];
let cur: number = 1;
for (const x of target) {
for (; cur < x; ++cur) {
ans.push('Push', 'Pop');
}
ans.push('Push');
++cur;
}
return ans;
}func buildArray(target []int, n int) (ans []string) {
cur := 1
for _, x := range target {
for ; cur < x; cur++ {
ans = append(ans, "Push", "Pop")
}
ans = append(ans, "Push")
cur++
}
return
}impl Solution {
pub fn build_array(target: Vec<i32>, n: i32) -> Vec<String> {
let mut ans = Vec::new();
let mut cur = 1;
for &x in &target {
while cur < x {
ans.push("Push".to_string());
ans.push("Pop".to_string());
cur += 1;
}
ans.push("Push".to_string());
cur += 1;
}
ans
}
}Complexity comparison
| 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). |
| Simulation | – |
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 |
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.