Build an Array With Stack Operations

Medium
381.

Build an Array With Stack Operations

Build an Array With Stack Operations is a medium coding problem on arrays, simulation and stack, asked in Amazon and Adobe interviews.

You are given a strictly increasing array target and an integer n. A stream reads the integers 1, 2, …, n in order, and you build a stack with two operations:

  • "Push" — push the next integer from the stream;
  • "Pop" — remove the top of the stack.

Return the shortest sequence of operations that leaves the stack equal to target. Stop as soon as the stack matches.

Example 1

Input
target = [1,3], n = 3
Output
["Push","Push","Pop","Push"]
Explanation
Read 1, then read 2 and discard it, then read 3.

Example 2

Input
target = [1,2,3], n = 3
Output
["Push","Push","Push"]

Example 3

Input
target = [1,2], n = 4
Output
["Push","Push"]

Constraints

  • 1 <= target.length <= 30
  • 1 <= target[i] <= n <= 40
  • target is strictly increasing.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} target
 * @param {number} n
 * @return {string[]}
 */
var buildArray = function(target, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Build an Array With Stack Operations — Problem & Solution

Build an Array With Stack Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Build an Array With Stack Operations is a medium coding problem on arrays, simulation and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Simulation, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a strictly increasing array target and an integer n. A stream reads the integers 1, 2, …, n in order, and you build a stack with two operations:

  • "Push" — push the next integer from the stream;
  • "Pop" — remove the top of the stack.

Return the shortest sequence of operations that leaves the stack equal to target. Stop as soon as the stack matches.

Example 1

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Read 1, then read 2 and discard it, then read 3.

Example 2

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3

Input: target = [1,2], n = 4
Output: ["Push","Push"]

Constraints

  • 1 <= target.length <= 30
  • 1 <= target[i] <= n <= 40
  • target is strictly increasing.

Hints for Build an Array With Stack Operations

  1. Hint 1

    Walk the stream from 1 upward, keeping a pointer into target.

  2. Hint 2

    Every number that is not the next target value is pushed and immediately popped.

  3. Hint 3

    Stop the moment the last target value has been pushed — trailing operations are never needed.

How to solve Build an Array With Stack Operations

Walk the stream 1..n with a pointer into target: every value that is not the next target is pushed and popped, the target value is pushed, and stop after the last target.

Approach

  1. For each want in target: while value < want, emit Push, Pop and increment; then emit Push and increment.

Why it works

The stream is consumed in order and target is increasing, so each intermediate number must be pushed and immediately removed. Stopping at the last target avoids useless trailing operations.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Iterating all the way to n emits extra pushes after the target is complete.

Reference solution

Python

def buildArray(target, n: int):
    out = []
    value = 1
    for want in target:
        while value < want:
            out.append("Push")
            out.append("Pop")
            value += 1
        out.append("Push")
        value += 1
    return out

Java

public static String[] buildArray(int[] target, int n) {
    List<String> out = new ArrayList<>();
    int value = 1;
    for (int want : target) {
        while (value < want) {
            out.add("Push");
            out.add("Pop");
            value++;
        }
        out.add("Push");
        value++;
    }
    return out.toArray(new String[0]);
}

C++

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> out;
    int value = 1;
    for (int want : target) {
        while (value < want) {
            out.push_back("Push");
            out.push_back("Pop");
            value++;
        }
        out.push_back("Push");
        value++;
    }
    return out;
}

JavaScript

var buildArray = function(target, n) {
    const out = [];
    let value = 1;
    for (let i = 0; i < target.length; i++) {
        while (value < target[i]) {
            out.push("Push");
            out.push("Pop");
            value++;
        }
        out.push("Push");
        value++;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure