Build an Array With Stack Operations

You are given a target array and an integer n. You have a stream of integers from 1 to n, and an initially empty stack. You can use two operations: "Push" (push the next integer from the stream onto the stack) and "Pop" (pop the top of the stack). Return a list of operations that builds the target array from the stream.

This is LeetCode 1441: Build an Array With Stack Operations, a medium problem that tests your ability to simulate stack operations against a stream of sequential input.

The problem

You receive integers one at a time from a stream: 1, 2, 3, ..., up to n. For each integer, you must decide whether to keep it (just "Push") or discard it ("Push" followed by "Pop"). The integers in target are strictly increasing and all fall within 1 to n. Your goal is to return the sequence of operations that leaves the stack matching target from bottom to top.

The approach

The key observation is that the stream always gives you numbers in order, and target is sorted and contains a subset of those numbers. So for each number from the stream, you check: is this number the next one I need in target? If yes, Push it and move to the next target element. If no, Push it and immediately Pop it to discard it. Once you have matched every element in target, you are done.

You do not actually need to maintain a stack data structure. The stream is sequential, and the target is sorted. You just need a pointer into the target array and a loop over the stream values.

Step-by-step walkthrough

Let's trace through target = [1, 3] with n = 3. The stream produces 1, 2, 3 in order.

Notice the pattern: every stream number gets a "Push". The numbers not in the target also get a "Pop" right after. The numbers in the target stay on the stack. The simulation ends as soon as all target elements have been placed.

The code

def buildArray(target, n):
    ops = []
    j = 0
    for i in range(1, n + 1):
        if j >= len(target):
            break
        ops.append("Push")
        if i == target[j]:
            j += 1
        else:
            ops.append("Pop")
    return ops

Here is what each piece does:

1. ops collects the list of operations. j is a pointer into target.
2. Loop through each integer i from 1 to n. If we have already matched all target elements (j >= len(target)), stop early.
3. Every integer from the stream must be pushed, so always append "Push".
4. If i matches target[j], this is a number we want to keep. Advance j to the next target element.
5. If i does not match target[j], this number needs to be discarded. Append "Pop" immediately after the "Push".

The early break when j >= len(target) is important. Once you have placed all target elements, there is no reason to read more from the stream.

Complexity analysis

Time is O(n) because you iterate through at most n stream values, doing constant work per value. Space is O(n) because the output list can contain up to 2 * n operations in the worst case (every number pushed and popped except the target elements).

The building blocks

1. Stream processing with a pointer

The core technique is processing a sequential stream while tracking your position in a separate target sequence. You maintain a pointer j into target and advance it whenever you find a match. This two-pointer-like pattern appears whenever you need to align elements from two ordered sequences.

j = 0
for i in range(1, n + 1):
    if i == target[j]:
        j += 1

2. Stack simulation

Even though you do not need an actual stack here, the problem is framed as stack operations. Understanding when "Push" keeps an element versus when "Push, Pop" discards it is a simulation skill. The same pattern of deciding to keep or discard elements appears in problems like Validate Stack Sequences, where you simulate an entire push/pop sequence to check validity.

3. Early termination

Once all target elements are matched, you break out of the loop. Recognizing when to stop early is a small but important optimization pattern. It prevents unnecessary work and keeps the output clean.

Edge cases

• Target equals the full stream: target = [1, 2, 3], n = 3. Every number is kept. The result is ["Push", "Push", "Push"] with no Pops at all.

• Target has just one element: target = [3], n = 3. Numbers 1 and 2 are pushed and popped. Number 3 is pushed and kept. Result: ["Push", "Pop", "Push", "Pop", "Push"].

• Target skips many numbers: target = [1, 5], n = 5. Numbers 2, 3, and 4 are all discarded. The output has several Push/Pop pairs between the two Push-only operations.

• Single element, n = 1: target = [1], n = 1. The simplest case. One Push, done.

From understanding to recall

You have read through the simulation and it makes sense. Walk the stream, push everything, pop what you do not need, stop when the target is complete. But will you remember the details in three weeks? The early break condition, the pointer advancement, the fact that every stream element must be pushed?

Spaced repetition locks in these details. You write the solution from scratch at increasing intervals until the pattern is automatic. When you see "build a sequence using stack operations" in an interview, the code flows out without hesitation.

Related posts

• Validate Stack Sequences - Simulate push and pop operations to verify if a sequence is valid
• Min Stack - Design a stack that supports push, pop, and retrieving the minimum element
• Evaluate Reverse Polish Notation - Use a stack to evaluate postfix expressions

CodeBricks breaks the build array with stack operations problem into its stream processing and stack simulation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a stack simulation question shows up in your interview, you do not think about it. You just write it.