LeetCode 1441 - Build an Array With Stack Operations

The problem gives us a strictly increasing array called target and an integer n. We are also given access to a stream of integers starting from 1 and ending at n. The numbers arrive in order, and once a number is skipped, we cannot go back to it.

leetcodemediumarraystacksimulation

LeetCode Problem 1441

Difficulty: 🟡 Medium
Topics: Array, Stack, Simulation

Solution

Problem Understanding

The problem gives us a strictly increasing array called target and an integer n. We are also given access to a stream of integers starting from 1 and ending at n. The numbers arrive in order, and once a number is skipped, we cannot go back to it.

We start with an empty stack and are allowed to perform only two operations:

  • "Push" adds the current stream number onto the stack.
  • "Pop" removes the top element from the stack.

The goal is to generate a sequence of operations such that the final stack contents exactly match the target array from bottom to top.

The important detail is that every number from the stream must first be pushed before it can be removed. This means that if a number appears in the stream but is not needed in target, we must still "Push" it and then immediately "Pop" it.

The input consists of:

  • target, a strictly increasing integer array
  • n, the maximum value in the stream [1, n]

The output is a list of strings representing the stack operations in order.

The constraints are relatively small:

  • target.length <= 100
  • n <= 100

These small limits mean that efficiency is not a major concern, but we still want a clean and optimal simulation.

The fact that target is strictly increasing is extremely important. It guarantees that the stream is processed in exactly one forward direction, and we never need to reconsider earlier numbers.

Several edge cases are important:

  • The target may contain consecutive numbers like [1,2,3], meaning no "Pop" operations are needed.
  • The target may skip numbers like [1,3], requiring temporary pushes and pops.
  • We must stop immediately once the stack equals target, even if more numbers remain in the stream.
  • The smallest possible input, such as target = [1], should still work correctly.

Approaches

Brute Force Approach

A brute force solution would attempt to simulate every possible sequence of "Push" and "Pop" operations while checking whether the resulting stack matches the target array.

For each incoming number from the stream, we could choose whether to keep it in the stack or remove it. This creates a branching decision tree where every number potentially doubles the number of possible operation sequences.

This approach is correct because it explores all valid operation combinations. Eventually, one of those combinations will produce the desired target stack.

However, this method is extremely inefficient. For each number, there are potentially two choices:

  • Keep it
  • Remove it

That leads to exponential growth in possibilities, approximately O(2^n) sequences in the worst case.

Even though the actual constraints are small, brute force is unnecessary because the structure of the problem gives us a deterministic strategy.

Optimal Approach

The key observation is that the stream arrives in sorted order, and target is also strictly increasing.

This means we never have ambiguity about what to do:

  • If the current stream number matches the next required target number, we keep it by performing "Push".
  • Otherwise, we must discard it using "Push" followed by "Pop".

We process numbers sequentially from 1 upward until we finish constructing the target array.

This works because every stream number must be consumed in order, and any number not present in target cannot remain in the stack.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explores all operation combinations
Optimal O(n) O(n) Greedy simulation using stream order

Algorithm Walkthrough

Step-by-Step Process

  1. Initialize an empty result list that will store the operations.

This list represents the exact sequence of "Push" and "Pop" operations we perform. 2. Maintain a pointer into the target array.

This pointer tracks which target value we are currently trying to build. 3. Iterate through the stream numbers starting from 1.

We continue processing until we have matched all elements in target. 4. For each stream number, always perform "Push" first.

Every stream value must be read and pushed before any decision can be made. 5. Compare the current stream number with the current target value.

If they are equal, we keep the value in the stack and move the target pointer forward. 6. If the numbers do not match, immediately perform "Pop".

This removes the unwanted value from the stack because it is not part of the target array. 7. Stop once all target elements have been matched.

The problem explicitly states that we should stop reading the stream once the stack equals the target.

Why it works

The algorithm works because both the stream and target are strictly increasing.

At every step, there are only two possibilities for the current stream number:

  • It belongs in the target, so we keep it.
  • It does not belong in the target, so we discard it immediately.

Since the stream cannot move backward, every skipped number must be removed right away. The greedy strategy is therefore forced and always produces a valid solution.

Python Solution

from typing import List

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        operations = []
        target_index = 0

        for current_number in range(1, n + 1):
            if target_index >= len(target):
                break

            operations.append("Push")

            if current_number == target[target_index]:
                target_index += 1
            else:
                operations.append("Pop")

        return operations

The implementation directly follows the simulation strategy.

We first create an empty operations list to store the answer. The variable target_index tracks which value in target we are currently trying to match.

We iterate through numbers from 1 to n. For every number, we always append "Push" because reading a stream value automatically requires pushing it onto the stack.

We then compare the current number against the expected target value.

If the values match, we keep the number and advance the target pointer.

If the values do not match, we append "Pop" to remove the unwanted number immediately.

The loop stops early once all target values have been matched, which avoids unnecessary processing beyond the required target.

Go Solution

func buildArray(target []int, n int) []string {
    operations := []string{}
    targetIndex := 0

    for currentNumber := 1; currentNumber <= n; currentNumber++ {
        if targetIndex >= len(target) {
            break
        }

        operations = append(operations, "Push")

        if currentNumber == target[targetIndex] {
            targetIndex++
        } else {
            operations = append(operations, "Pop")
        }
    }

    return operations
}

The Go implementation mirrors the Python logic very closely.

Slices are used for dynamically storing operations. Since Go slices automatically resize with append, no manual memory management is needed.

Unlike Python, Go does not require explicit type hints because the compiler infers types from variable declarations.

There are no overflow concerns because all values are very small under the problem constraints.

Worked Examples

Example 1

Input:

target = [1,3]
n = 3
Stream Number Action Operations Stack State
1 Keep Push [1]
2 Discard Push, Pop [1]
3 Keep Push [1,3]

Final output:

["Push","Push","Pop","Push"]

Example 2

Input:

target = [1,2,3]
n = 3
Stream Number Action Operations Stack State
1 Keep Push [1]
2 Keep Push [1,2]
3 Keep Push [1,2,3]

Final output:

["Push","Push","Push"]

Example 3

Input:

target = [1,2]
n = 4
Stream Number Action Operations Stack State
1 Keep Push [1]
2 Keep Push [1,2]

At this point the stack equals the target, so we stop immediately.

Final output:

["Push","Push"]

Complexity Analysis

Measure Complexity Explanation
Time O(n) We process each stream number at most once
Space O(n) The operations list may contain up to 2n entries

The algorithm performs a single pass through the stream numbers. Each number results in either one operation ("Push") or two operations ("Push" and "Pop").

The auxiliary space comes entirely from storing the output operations list.

Test Cases

from typing import List

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        operations = []
        target_index = 0

        for current_number in range(1, n + 1):
            if target_index >= len(target):
                break

            operations.append("Push")

            if current_number == target[target_index]:
                target_index += 1
            else:
                operations.append("Pop")

        return operations

solution = Solution()

# Provided examples
assert solution.buildArray([1, 3], 3) == ["Push", "Push", "Pop", "Push"]  # skips one value
assert solution.buildArray([1, 2, 3], 3) == ["Push", "Push", "Push"]  # all consecutive
assert solution.buildArray([1, 2], 4) == ["Push", "Push"]  # stops early

# Smallest possible input
assert solution.buildArray([1], 1) == ["Push"]  # minimal case

# Single target element not at start
assert solution.buildArray([3], 3) == [
    "Push", "Pop",
    "Push", "Pop",
    "Push"
]  # multiple skipped values

# Consecutive values after skips
assert solution.buildArray([2, 3, 4], 4) == [
    "Push", "Pop",
    "Push",
    "Push",
    "Push"
]  # initial skip then consecutive keeps

# Large gaps
assert solution.buildArray([2, 4], 4) == [
    "Push", "Pop",
    "Push",
    "Push", "Pop",
    "Push"
]  # multiple discarded values

# Full range target
assert solution.buildArray([1, 2, 3, 4, 5], 5) == [
    "Push", "Push", "Push", "Push", "Push"
]  # every number retained
Test Why
[1,3], n=3 Validates skipping intermediate numbers
[1,2,3], n=3 Validates consecutive target values
[1,2], n=4 Ensures early stopping works
[1], n=1 Smallest valid input
[3], n=3 Tests repeated push-pop operations
[2,3,4], n=4 Tests initial skipped values
[2,4], n=4 Tests multiple non-consecutive skips
[1,2,3,4,5], n=5 Tests retaining every stream value

Edge Cases

One important edge case occurs when the target contains every number consecutively from 1 onward, such as [1,2,3]. In this situation, no "Pop" operations are required. A buggy implementation might still attempt unnecessary removals. The current implementation correctly performs only "Push" operations because every stream number matches the current target value.

Another important edge case is when many numbers must be skipped before reaching the desired target value, such as [5]. This can expose bugs where skipped values are not properly removed from the stack. The algorithm handles this by always performing "Push" first and then immediately "Pop" whenever the current number does not match the target.

A third critical edge case is early termination. For example, with target = [1,2] and n = 100, we must stop immediately after building the target. A naive implementation might continue processing the stream unnecessarily. The solution avoids this by breaking the loop as soon as all target elements are matched.