Problem

Solution

Intuition

This is a pretty easy question with only basic array operations needed in order to create the stack-like structure that the problem asks for.

Approach

There are two conditions that each number will have as we iterate through the numbers from $1$ to $n$. Either:

1. The number is part of target and we add a Push operation to the result and iterate our pointer to keep track of the position in target (remember this is unsynced as while the array is strictly increasing, numbers may be skipped) or
2. the number is not part of target and we add a Push and Pop operation as each number gets pushed before it is removed.

Then we return the result.

Complexity

• Time complexity: $O(n)$ time complexity as we iterate from $1$ to $n$ once and do a constant set of operations.
• Space complexity: $O(n)$ space complexity to store the result.

Code

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        res = []
        pointer = 0
        for i in range(1,n+1):
            if i == target[pointer]:
                res.append("Push")
                pointer += 1
            else:
                res.append("Push")
                res.append("Pop")
            if pointer == len(target):
                return res