Code Implementation

class Solution:
    def buildArray(self, target, n):
        res = []
        curr = 1
        i = 0
        while i < len(target):
            if curr == target[i]:
                res.append("Push")
                i += 1
            else:
                res.append("Push")
                res.append("Pop")
            curr += 1
        return res
      

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> res;
        int curr = 1, i = 0;
        while (i < target.size()) {
            if (curr == target[i]) {
                res.push_back("Push");
                ++i;
            } else {
                res.push_back("Push");
                res.push_back("Pop");
            }
            ++curr;
        }
        return res;
    }
};
      

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int curr = 1, i = 0;
        while (i < target.length) {
            if (curr == target[i]) {
                res.add("Push");
                i++;
            } else {
                res.add("Push");
                res.add("Pop");
            }
            curr++;
        }
        return res;
    }
}
      

var buildArray = function(target, n) {
    let res = [];
    let curr = 1, i = 0;
    while (i < target.length) {
        if (curr === target[i]) {
            res.push("Push");
            i++;
        } else {
            res.push("Push");
            res.push("Pop");
        }
        curr++;
    }
    return res;
};
      

Problem Description

You are given a strictly increasing array target containing integers from 1 to n (inclusive), and an integer n. You have an empty stack and can perform two operations: Push (add the next number in sequence from 1 to n onto the stack), and Pop (remove the top element from the stack). Your goal is to build the target array by simulating these stack operations in order, starting from 1 up to n (but you may stop early if target is completed).

For each number from 1 to n:

• If the number is in target, you must Push it onto the stack.
• If the number is not in target, you must Push it and then immediately Pop it.

Thought Process

At first glance, you might consider simulating the stack fully, pushing and popping values as needed, or even trying to generate all possible sequences. However, the problem's constraints and the strictly increasing property of target mean that for each value from 1 to n, you know exactly what to do:

• If the current number matches the next needed value in target, you Push it and move to the next target value.
• If it doesn't match, you Push and immediately Pop it, effectively skipping it.

This leads to a direct and efficient solution, where you only need to iterate through numbers from 1 up to the last value in target (since all target values are between 1 and n).

Solution Approach

Let's break down the solution step by step:

1. Initialize: Create an empty result list to store the operations. Set a pointer (or index) to track your position in the target array. Start a counter at 1 to represent the next number to consider.
2. Iterate: For each number from 1 up to target[-1] (the largest number in target):
   • If the current number matches the current target value, append "Push" to the result and move to the next target value.
   • If not, append "Push" and then "Pop" to the result (since you must process numbers in order, but don't want to keep this one).
3. Stop Early: Once all values in target are processed, you can stop. There's no need to continue up to n.
4. Return: Output the list of operations.

This approach is both simple and efficient because it leverages the properties of the input: strictly increasing and unique values in target.

Example Walkthrough

Let's walk through an example with target = [2, 3, 4] and n = 4:

1. Current number = 1:
   target[0] = 2, so 1 is not in target.
   Operations: Push, Pop (stack is unchanged).
2. Current number = 2:
   target[0] = 2, so 2 is in target.
   Operation: Push (stack: [2]).
3. Current number = 3:
   target[1] = 3, so 3 is in target.
   Operation: Push (stack: [2, 3]).
4. Current number = 4:
   target[2] = 4, so 4 is in target.
   Operation: Push (stack: [2, 3, 4]).

So the output would be: ["Push", "Pop", "Push", "Push", "Push"].

Time and Space Complexity

Brute-force approach: If you tried to generate all possible stack operation sequences, the time and space complexity would be exponential, which is infeasible for even moderate values of n.

Optimized approach (used here):

• Time Complexity: O(m), where m is the largest value in target. This is because we only process numbers up to target[-1], and at each step we do a constant amount of work.
• Space Complexity: O(m), for storing the result list of operations, which is at most twice as long as target (in the case where every non-target element is pushed and popped).

Summary

The key insight is to leverage the strictly increasing nature of target and the requirement to process numbers in order from 1 to n. By comparing each number with the next target value, we can efficiently decide whether to "Push" or "Push" and "Pop". This direct approach avoids unnecessary simulation and results in a simple, efficient, and elegant solution.