Problem

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

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

Return the target array.

It is guaranteed that the insertion operations will be valid.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2

1
2
3
4
5
6
7
8
9

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3

1
2

Input: nums = [1], index = [0]
Output: [1]

Constraints

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i

Solution

Method 1 – Simulation with List Insertion

Intuition

The key idea is to simulate the process described in the problem: for each value in nums, insert it at the specified position in index. This is efficient for small arrays and directly models the problem statement.

Approach

  1. Initialize an empty list ans.
  2. Iterate through each pair (num, idx) from nums and index:
    • Insert num at position idx in ans.
  3. Return ans after all insertions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            ans.insert(ans.begin() + index[i], nums[i]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func createTargetArray(nums []int, index []int) []int {
    ans := []int{}
    for i, v := range nums {
        idx := index[i]
        ans = append(ans, 0)
        copy(ans[idx+1:], ans[idx:])
        ans[idx] = v
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            ans.add(index[i], nums[i]);
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) res[i] = ans.get(i);
        return res;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun createTargetArray(nums: IntArray, index: IntArray): IntArray {
        val ans = mutableListOf<Int>()
        for (i in nums.indices) {
            ans.add(index[i], nums[i])
        }
        return ans.toIntArray()
    }
}
1
2
3
4
5
6

class Solution:
    def createTargetArray(self, nums: list[int], index: list[int]) -> list[int]:
        ans = []
        for v, i in zip(nums, index):
            ans.insert(i, v)
        return ans
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn create_target_array(nums: Vec<i32>, index: Vec<i32>) -> Vec<i32> {
        let mut ans = Vec::new();
        for (v, &i) in nums.iter().zip(index.iter()) {
            ans.insert(i as usize, *v);
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    createTargetArray(nums: number[], index: number[]): number[] {
        const ans: number[] = [];
        for (let i = 0; i < nums.length; i++) {
            ans.splice(index[i], 0, nums[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), as each insertion may take O(n) time and there are n insertions.
  • 🧺 Space complexity: O(n), for the result array.