# Build an Array With Stack Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/build-an-array-with-stack-operations)
Canonical: https://scaleengineer.com/dsa/problems/build-an-array-with-stack-operations
**Data structures:** Array, Stack
---
## 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 <= 100`
* `1 <= n <= 100`
* `1 <= target[i] <= n`
* `target` is strictly increasing.

# Approaches
## Simulation with Explicit Stack
This approach directly simulates the process described in the problem. We use an explicit stack data structure to keep track of the current state of the stack. We iterate through the numbers from the stream `[1, n]`, push each number onto our simulated stack, and record a "Push" operation. Then, we compare the top of the stack with the current element we need for the `target` array. If they don't match, it means the number we just pushed is not needed, so we pop it and record a "Pop" operation. We continue this process until our simulated stack matches the `target` array.
**Time:** O(n), or more precisely O(target[target.length-1]). The loop iterates from 1 up to the last value in the `target` array, which is at most `n`. All operations inside the loop are O(1). · **Space:** O(n). The space is required for the output `operations` list, which can have up to `2 * n` elements. Additionally, the explicit `stack` can store up to `target.length` elements. Thus, the total space complexity is O(n).
**Pros:** It's a very intuitive approach as it directly models the actions described in the problem statement.; The logic is straightforward to follow and implement.
**Cons:** It uses extra space for an explicit stack, which is not strictly necessary to generate the list of operations.; Slightly less memory-efficient compared to an approach that avoids the explicit stack.
### Explanation
We can solve this problem by faithfully simulating the entire process. The algorithm proceeds as follows:

- We initialize an empty list `operations` to store the sequence of operations and an empty `stack` to mimic the stack in the problem.
- We also use a pointer, `targetIndex`, initialized to `0`, to keep track of which element from the `target` array we are currently trying to match.
- We then iterate through the numbers from the stream, from `1` up to `n`. For each number `i`:
  1. We perform a "Push" operation. This involves adding `i` to our `stack` and appending the string "Push" to our `operations` list.
  2. After pushing, we check if the number `i` is the one we need for our target. We compare `i` with `target[targetIndex]`.
  3. If `i` is equal to `target[targetIndex]`, it means we have successfully placed a correct number on the stack. We then advance our goal by incrementing `targetIndex`.
  4. If `i` is not equal to `target[targetIndex]`, it means `i` is an extraneous number that shouldn't be in the final stack. We must immediately remove it by performing a "Pop" operation. This involves popping from our `stack` and appending "Pop" to the `operations` list.
- The process continues until we have successfully built the entire `target` array, which is signified by `targetIndex` reaching the length of the `target` array. At this point, we can stop and return the collected `operations`.

Here is the implementation in Java:
```java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> operations = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int targetIndex = 0;

        for (int i = 1; i <= n && targetIndex < target.length; i++) {
            stack.push(i);
            operations.add("Push");

            if (stack.peek() == target[targetIndex]) {
                targetIndex++;
            } else {
                stack.pop();
                operations.add("Pop");
            }
        }
        return operations;
    }
}
```
### Algorithm
- Initialize an empty list `operations`, an empty `stack`, and a `targetIndex` to 0.
- Iterate with `currentNum` from 1 to `n`, but stop if `targetIndex` reaches `target.length`.
- In each iteration, push `currentNum` to the `stack` and add "Push" to `operations`.
- Check if the top of the stack matches `target[targetIndex]`.
- If it matches, increment `targetIndex`.
- If it does not match, pop from the `stack` and add "Pop" to `operations`.
- After the loop, return the `operations` list.

## Two Pointers / Greedy Approach
This approach optimizes the simulation by realizing that we don't need an explicit stack. The state of the stack is implicitly determined by the numbers we have processed from the stream and the `target` array. We can use one pointer for the stream of numbers `[1, n]` and another pointer for the `target` array. We iterate through the stream and decide whether to "Push" or "Push" then "Pop" based on whether the current stream number matches the current target number.
**Time:** O(n), or more precisely O(target[target.length-1]). The loop runs up to the last value in the `target` array, which is at most `n`. The operations inside the loop are O(1). · **Space:** O(n). The space complexity is determined by the size of the output list, `operations`. In the worst-case scenario, the number of operations is proportional to `n`. This is optimal as it matches the space required for the return value.
**Pros:** More space-efficient as it avoids the overhead of an explicit stack data structure.; The logic is simple, clean, and directly constructs the required list of operations.; Generally faster due to fewer operations (no actual stack manipulation).
**Cons:** The logic might be slightly less obvious than a direct simulation, as it relies on understanding the implicit state of the stack.
### Explanation
A more efficient way to solve this problem is to notice that we don't actually need to maintain a stack. We only need to generate the list of operations. The fact that the `target` array is strictly increasing is a key observation.

- We can use two pointers: one, `currentNum`, that represents the number being read from the stream (from `1` to `n`), and another, `targetIndex`, that points to the current element we are trying to match in the `target` array.
- We iterate `currentNum` from `1` upwards. For each `currentNum`:
  1. We must read it from the stream, which corresponds to a "Push" operation. So, we add "Push" to our result list.
  2. We then compare `currentNum` with the number we are currently looking for, `target[targetIndex]`.
  3. If `currentNum == target[targetIndex]`, it means this number is part of the final sequence. We 'keep' it by simply moving on to the next target element, i.e., incrementing `targetIndex`.
  4. If `currentNum != target[targetIndex]`, it implies that `currentNum` is a number that appears in the stream before the required `target[targetIndex]`. Since it's not needed, we must immediately pop it. So, we add a "Pop" operation to our result list. We do not increment `targetIndex` because we are still looking for `target[targetIndex]`.
- We continue this process until we have found all the numbers in the `target` array (i.e., `targetIndex == target.length`). At this point, we can stop, as any further operations are unnecessary.

This greedy approach is more efficient as it avoids the overhead of managing a stack data structure.

Here is the Java implementation:
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> operations = new ArrayList<>();
        int targetIndex = 0; // Pointer for the target array

        // currentNum represents the number from the stream [1, 2, ..., n]
        for (int currentNum = 1; currentNum <= n && targetIndex < target.length; currentNum++) {
            // We always read the current number from the stream and push it.
            operations.add("Push");

            if (currentNum == target[targetIndex]) {
                // The number matches the target, so we keep it and move to the next target.
                targetIndex++;
            } else {
                // The number does not match, so we must pop it.
                operations.add("Pop");
            }
        }
        return operations;
    }
}
```
### Algorithm
- Initialize an empty list `operations` and a `targetIndex` to 0.
- Iterate with `currentNum` from 1 to `n`, but stop if `targetIndex` reaches `target.length`.
- In each iteration, add "Push" to `operations`.
- Check if `currentNum` is equal to `target[targetIndex]`.
- If it is, increment `targetIndex`.
- If it is not, add "Pop" to `operations`.
- After the loop, return the `operations` list.

# Solutions
### Java

```java
class Solution {
public
  List<String> buildArray(int[] target, int n) {
    int cur = 0;
    List<String> ans = new ArrayList<>();
    for (int v : target) {
      while (++cur < v) {
        ans.add("Push");
        ans.add("Pop");
      }
      ans.add("Push");
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> buildArray(vector<int> &target, int n) {
    int cur = 0;
    vector<string> ans;
    for (int &v : target) {
      while (++cur < v) {
        ans.emplace_back("Push");
        ans.emplace_back("Pop");
      }
      ans.emplace_back("Push");
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]: cur, ans = 0, [] for v in target: cur += 1 while cur < v: ans . extend(['Push', 'Pop']) cur += 1 ans . append('Push') return ans

```