Construct a target array using only push and pop operations while scanning numbers from 1 to in order.
Problem
You are given a target array of distinct integers in strictly increasing order and an integer .
Start with an empty stack-like structure and read the numbers from $1n$ in increasing order. For each number you read, you may:
- Push it into the structure, or
- Pop it immediately after pushing it.
Your goal is to build the exact target array in order. For every number from $1n$, output the sequence of operations needed to construct target using only Push and Pop.
If a number is not part of target, it should be pushed and then popped right away.
Preptin Note
This is a direct simulation problem: process the numbers in order and decide whether each one should stay in the final array.
Input Format
- An integer array
targetin strictly increasing order. - An integer
n.
Output Format
Return a list of strings containing the operations in order. Each operation is either "Push" or "Pop".
Constraints
targetis strictly increasing.
Example 1
Input
target = [1,3], n = 3
Output
["Push","Push","Pop","Push"]
Explanation
Read 1: it is needed, so keep it. Read 2: it is not in the target, so push then pop. Read 3: it is needed, so keep it. The operations build [1,3].
Example 2
Input
target = [1,2,3], n = 3
Output
["Push","Push","Push"]
Explanation
Every number from 1 to 3 is part of the target, so each one is pushed and kept.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.