Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in one sentence

Starting with an empty stack, consume the stream 1, 2, ..., n in order and emit Push and Pop operations so the stack becomes exactly the strictly increasing array target—then stop immediately.

The stream constraint is the whole problem. Its next value cannot be chosen or revisited: reading a value always pushes it, and the only way to discard an unwanted value is to pop it before moving on.

Deriving the greedy simulation

Consider the next stream value, current_value.

  • If it is the next value required by target, emit Push and keep it.
  • Otherwise, emit Push followed by Pop, because that value cannot appear in the final stack.

Once the last target value has been kept, stop. Reading anything further would violate the rule that operations end as soon as the stack equals target.

For target = [1, 3], the stream is handled like this:

  1. Read 1: emit Push and keep it.
  2. Read 2: emit Push, then Pop because 2 is not wanted.
  3. Read 3: emit Push and stop.

The result is ['Push', 'Push', 'Pop', 'Push'].

This greedy choice is forced, not merely convenient. Every integer from 1 through target[-1] must be read. Each read requires one Push; every read value missing from target must later be removed with one Pop. No valid solution can use fewer operations, and the simulation performs exactly those necessary operations.

Python solution

from typing import List


class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        """Return stack operations that construct target from the stream 1..n."""
        operations: List[str] = []
        target_index = 0

        for current_value in range(1, n + 1):
            # Reading a stream value always pushes it onto the stack.
            operations.append("Push")

            if current_value == target[target_index]:
                # Keep required values. Stop as soon as target is complete.
                target_index += 1
                if target_index == len(target):
                    break
            else:
                # Discard values that do not belong in the final stack.
                operations.append("Pop")

        return operations

Let $m = \text{target}[-1]$, the final value that must be read. The algorithm takes $O(m)$ time. Its operation list contains $m$ pushes and $m - |\text{target}|$ pops, so the returned output itself uses $O(m)$ space. Excluding that required output, the algorithm uses $O(1)$ auxiliary space.

Why stopping at the last target value matters

The parameter n only guarantees how far the stream could continue; it does not require consuming all n values. Because target is strictly increasing and every target value is at most n, reaching its final value means every earlier target value has already been kept in the correct order.

At that instant the stack equals target. Continuing to read would append an unwanted larger value, and even a compensating Pop would be an operation performed after the required stopping point. The early break therefore enforces part of the problem contract, not just an optimization.

Interview follow-ups

Why is the operation sequence optimal?

To reach the largest target value $m$, the stream forces the algorithm to read every value from $1$ through $m$. Reading each one costs a Push, so every solution needs at least $m$ pushes. Exactly $|\text{target}|$ of those values belong in the final stack; each of the other $m - |\text{target}|$ values must be removed, requiring at least that many pops.

The greedy simulation meets both lower bounds exactly. Its total operation count is therefore $2m - |\text{target}|$, and no valid solution can be shorter.

What if target is not strictly increasing?

The fixed increasing stream can produce only an increasing sequence of retained values. A duplicate or a descending pair in target is therefore impossible to construct because consumed stream values cannot be replayed.

In a production API without LeetCode’s input guarantees, validate that target is nonempty, strictly increasing, starts at least at 1, and ends at most at n. Validation costs $O(|\text{target}|)$ time and $O(1)$ space before running the same simulation.

What if n is extremely large?

The algorithm never needs to iterate to n; it stops after reading target[-1]. Its running time depends on the largest required value and on the unavoidable output size, not on the full upper bound of the stream.

If target[-1] is also enormous, returning individual operation strings is inherently expensive: the answer itself contains one Push for every consumed value. A different interface would be needed to improve practical memory use.

Can the operations be streamed instead of stored?

Yes. A generator can yield Push and, for skipped values, Pop as each stream value is processed. That reduces auxiliary memory to $O(1)$ because the caller can consume operations immediately.

The total time and number of emitted operations do not change. LeetCode requires a list, so the submitted solution must materialize the $O(m)$ output.

Can the answer be represented more compactly?

If the consumer accepts a compressed format, each gap before a target value can be represented by a count of repeated Push, Pop pairs, followed by one retained Push. This uses $O(|\text{target}|)$ records rather than one string per operation.

Decompression still produces the same $2m - |\text{target}|$ primitive operations. The improvement is in representation and transmission, not in the work performed by the conceptual stack machine.

What if the source is an arbitrary increasing stream rather than 1 through n?

Advance through the source and compare each value with the next target value. Emit Push, Pop for smaller unwanted values and Push for a match. If the source passes a required target value or ends first, construction is impossible.

This is a subsequence check combined with the same simulation. It takes linear time in the consumed portion of the source and constant auxiliary space besides the returned operations.

Takeaway

The clean solution comes from respecting the stream literally. Every value up to the last target element must be pushed; required values stay, and all others are popped immediately. Once that forced structure is recognized, the implementation and its optimality proof are both straightforward.