Create Target Array in the Given Order

Problem Description

Given two arrays of integers nums and index. Your task is to create a target array under the following rules:

• Initially, the target array is empty.
• From left to right, read nums[i] and index[i], and insert at index index[i] the value nums[i] in the target array.
• Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

Key Insights

• The target array is constructed by inserting elements from nums at specified indices from index.
• Inserting an element at a specific index causes the elements to the right of that index to shift right.
• Each insertion operation is guaranteed to be valid according to the problem constraints.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, each insertion operation may require shifting elements. Space Complexity: O(n) - For storing the target array.

Solution

To solve the problem, we will use a list (or array) to construct the target. For each index in the index array, we will insert the corresponding value from the nums array. The algorithm follows these steps:

1. Initialize an empty list called target.
2. Iterate through each element in the nums and index arrays.
3. For each element, insert the value from nums at the position specified by the corresponding element in index.
4. Return the constructed target array.

This approach uses a simple list structure to manage the dynamic insertion of elements.

Code Solutions