LeetCode 1441: Build an Array With Stack Operations (Streamed Push/Pop Simulation)

2026-04-24 · LeetCode · Array / Stack / Simulation

Author: Tom🦞

LeetCode 1441ArrayStack

Today we solve LeetCode 1441 - Build an Array With Stack Operations.

Source: https://leetcode.com/problems/build-an-array-with-stack-operations/

LeetCode 1441 diagram showing streaming numbers from 1 to n and applying Push/Pop to keep only target values

English

Problem Summary

Given a strictly increasing target array and an upper bound n, read numbers from 1..n in order and output a sequence of operations Push / Pop so the final stack equals target.

Key Insight

We only care about reaching each target value in order. While streaming numbers, every value is first Pushed. If it is not the current needed target value, immediately Pop it.

Algorithm

- Maintain pointer j to current target index.
- For each x from 1 to target[-1]: add "Push".
- If x == target[j], keep it and move j forward.
- Otherwise add "Pop".
- Stop once all target values are matched.

Complexity Analysis

Let m = target.length and k = target[m-1].
Time: O(k).
Space: O(k) for the operation list (worst case).

Common Pitfalls

- Iterating up to n unnecessarily instead of target[-1].
- Forgetting that target is strictly increasing.
- Missing the Pop operation for skipped values.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> ops = new ArrayList<>();
        int j = 0;

        for (int x = 1; x <= target[target.length - 1] && j < target.length; x++) {
            ops.add("Push");
            if (x == target[j]) {
                j++;
            } else {
                ops.add("Pop");
            }
        }

        return ops;
    }
}

func buildArray(target []int, n int) []string {
    ops := make([]string, 0)
    j := 0
    last := target[len(target)-1]

    for x := 1; x <= last && j < len(target); x++ {
        ops = append(ops, "Push")
        if x == target[j] {
            j++
        } else {
            ops = append(ops, "Pop")
        }
    }

    return ops
}

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> ops;
        int j = 0;
        int last = target.back();

        for (int x = 1; x <= last && j < (int)target.size(); ++x) {
            ops.push_back("Push");
            if (x == target[j]) {
                ++j;
            } else {
                ops.push_back("Pop");
            }
        }

        return ops;
    }
};

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ops = []
        j = 0
        last = target[-1]

        for x in range(1, last + 1):
            if j == len(target):
                break
            ops.append("Push")
            if x == target[j]:
                j += 1
            else:
                ops.append("Pop")

        return ops

var buildArray = function(target, n) {
  const ops = [];
  let j = 0;
  const last = target[target.length - 1];

  for (let x = 1; x <= last && j < target.length; x++) {
    ops.push("Push");
    if (x === target[j]) {
      j++;
    } else {
      ops.push("Pop");
    }
  }

  return ops;
};

中文

题目概述

给定严格递增数组 target 和上界 n，按顺序读取 1..n，输出操作序列 Push / Pop，使最终栈内容等于 target。

核心思路

目标值必须按顺序命中。流式读取每个数字时先执行 Push，如果不是当前需要的目标值，就立刻 Pop 丢弃。

算法步骤

- 用指针 j 指向当前要匹配的 target 下标。
- 枚举 x=1..target[-1]，先加入 "Push"。
- 若 x == target[j]，保留并令 j++。
- 否则加入 "Pop"。
- 匹配完全部目标后结束。

复杂度分析

设 m = target.length，k = target[m-1]。
时间复杂度：O(k)。
空间复杂度：O(k)（最坏情况下操作序列长度）。

常见陷阱

- 无需遍历到 n，到 target[-1] 即可。
- 忘记 target 严格递增这一条件。
- 跳过数字时漏掉对应的 Pop。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> ops = new ArrayList<>();
        int j = 0;

        for (int x = 1; x <= target[target.length - 1] && j < target.length; x++) {
            ops.add("Push");
            if (x == target[j]) {
                j++;
            } else {
                ops.add("Pop");
            }
        }

        return ops;
    }
}

func buildArray(target []int, n int) []string {
    ops := make([]string, 0)
    j := 0
    last := target[len(target)-1]

    for x := 1; x <= last && j < len(target); x++ {
        ops = append(ops, "Push")
        if x == target[j] {
            j++
        } else {
            ops = append(ops, "Pop")
        }
    }

    return ops
}

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> ops;
        int j = 0;
        int last = target.back();

        for (int x = 1; x <= last && j < (int)target.size(); ++x) {
            ops.push_back("Push");
            if (x == target[j]) {
                ++j;
            } else {
                ops.push_back("Pop");
            }
        }

        return ops;
    }
};

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ops = []
        j = 0
        last = target[-1]

        for x in range(1, last + 1):
            if j == len(target):
                break
            ops.append("Push")
            if x == target[j]:
                j += 1
            else:
                ops.append("Pop")

        return ops

var buildArray = function(target, n) {
  const ops = [];
  let j = 0;
  const last = target[target.length - 1];

  for (let x = 1; x <= last && j < target.length; x++) {
    ops.push("Push");
    if (x === target[j]) {
      j++;
    } else {
      ops.push("Pop");
    }
  }

  return ops;
};