Code Implementation

class Solution:
    def createTargetArray(self, nums, index):
        target = []
        for num, idx in zip(nums, index):
            target.insert(idx, num)
        return target
      

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> target;
        for (int i = 0; i < nums.size(); ++i) {
            target.insert(target.begin() + index[i], nums[i]);
        }
        return target;
    }
};
      

class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> target = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            target.add(index[i], nums[i]);
        }
        int[] res = new int[target.size()];
        for (int i = 0; i < target.size(); i++) {
            res[i] = target.get(i);
        }
        return res;
    }
}
      

var createTargetArray = function(nums, index) {
    let target = [];
    for (let i = 0; i < nums.length; i++) {
        target.splice(index[i], 0, nums[i]);
    }
    return target;
};
      

Problem Description

You are given two arrays of integers, nums and index, both of the same length. You need to create a new array called target by inserting the value nums[i] at position index[i] in target for each i from 0 to nums.length - 1.

The process must be completed in order: for each step, insert the current number at the specified position in the current state of the target array. It is guaranteed that the insertion index is always valid (i.e., between 0 and the current length of target).

• Each element from nums is used exactly once.
• There is only one valid way to build the target array.
• Do not reuse elements or skip steps.

Thought Process

At first glance, the problem looks like it could be solved by creating an empty array and inserting elements one by one at the required positions. However, inserting into an array at arbitrary positions can be costly in some languages, especially if not using a dynamic array/list structure.

The brute-force approach is to simulate the process exactly as described: for each position, insert the value at the specified index. Since the constraints are small (array sizes are reasonable), this direct simulation is acceptable. There is no need for complex optimizations or data structures.

The main consideration is to ensure that after each insertion, the target array remains valid and that subsequent insertions use the updated array.

Solution Approach

Let's break down the solution step by step:

1. Initialize an empty array: Start with an empty list or array to build the target array.
2. Iterate through the input arrays: For each index i, take nums[i] and insert it into target at position index[i].
3. Insertion: Use the language's built-in method for inserting at a specific position (e.g., insert in Python lists, add(index, value) for Java ArrayList, splice in JavaScript arrays, or insert for C++ vectors).
4. Repeat: Continue this process for every element in nums and index.
5. Return the result: After all insertions, the target array will be complete and can be returned.

This approach directly follows the problem's instructions and is efficient enough for the given constraints. We use dynamic arrays/lists because they allow for efficient insertions compared to fixed-size arrays.

Example Walkthrough

Let's work through an example:

Suppose nums = [0,1,2,3,4] and index = [0,1,2,2,1].

• Step 0: Insert 0 at index 0 → [0]
• Step 1: Insert 1 at index 1 → [0, 1]
• Step 2: Insert 2 at index 2 → [0, 1, 2]
• Step 3: Insert 3 at index 2 → [0, 1, 3, 2]
• Step 4: Insert 4 at index 1 → [0, 4, 1, 3, 2]

Final target: [0, 4, 1, 3, 2]

At each step, the array grows and elements at or after the insertion index are shifted to the right to make space for the new element.

Time and Space Complexity

• Brute-force Approach: For each insertion at position i, elements after index index[i] need to be shifted. In the worst case, this is O(n) per insertion, leading to O(n^2) time for n insertions.
• Space Complexity: We use an extra array of size n for target, so space is O(n).
• Optimized Approach: For this problem, the brute-force is sufficient due to small constraints. Advanced data structures (like linked lists or balanced BSTs) could reduce insertion time but are unnecessary here.

In summary: Time Complexity: O(n^2). Space Complexity: O(n).

Summary

The "Create Target Array in the Given Order" problem is a direct simulation of inserting elements into an array at specified positions. The key insight is to use dynamic array operations to handle insertions efficiently for the given constraints. The approach is straightforward, requiring only basic array/list manipulation, and demonstrates the importance of following problem instructions precisely. The solution is elegant in its simplicity and directness.