Create Target Array in the Given Order

Easy

#1287Time: O(N^2), where N is the number of elements. The outer loop runs N times. In each iteration `i`, the inner loop for shifting can run up to `i` times in the worst case (when `index[i]` is 0). The total number of operations is proportional to the sum 1 + 2 + ... + (N-1), which is O(N^2).Space: O(N) to store the target array. If the space for the output is not considered, the space complexity is O(1).1 company

Data structures

Array

Companies

Visa

Prompt

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.

Example 1:

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:

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:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the insertion process using a standard fixed-size array. Since inserting into the middle of a primitive array is not a built-in operation, we must manually implement the logic to shift elements to the right to create a space for each new element. We iterate through the given nums and index arrays, and for each pair, we perform the shift-and-insert operation on our target array.

Algorithm

Create a result array target of size n, where n is the length of the input arrays.
Initialize a variable size to 0, which will keep track of the number of elements currently in the target array.
Iterate through the input arrays from i = 0 to n-1:
- Get the value nums[i] and the insertion index index[i].
- To make space for the new element at index[i], shift all elements from that index to the current end of the array (size - 1) one position to the right. This must be done in reverse order (from right to left) to avoid overwriting data.
- Insert nums[i] at index[i].
- Increment the size of the array.
After the loop completes, return the target array.

Walkthrough

We initialize a target array with the final required size. We also use a size variable to track how many elements have been inserted so far. For each element nums[i] to be inserted at index[i], we first shift all elements from index[i] up to the current end of the populated part of the array (size - 1) one step to the right. This opens up a spot at index[i], where we can then place nums[i]. This process is repeated for all elements.

1class Solution {2    public int[] createTargetArray(int[] nums, int[] index) {3        int n = nums.length;4        int[] target = new int[n];5        int size = 0; // current number of elements in target6 7        for (int i = 0; i < n; i++) {8            int idx = index[i];9            int val = nums[i];10 11            // Shift elements to the right to make space for the new element12            // We shift elements from the current end (size-1) down to idx13            for (int j = size; j > idx; j--) {14                target[j] = target[j - 1];15            }16 17            // Insert the new element at the specified index18            target[idx] = val;19            20            // Increment the size of the populated part of the array21            size++;22        }23 24        return target;25    }26}

Complexity

Time

O(N^2), where N is the number of elements. The outer loop runs N times. In each iteration `i`, the inner loop for shifting can run up to `i` times in the worst case (when `index[i]` is 0). The total number of operations is proportional to the sum 1 + 2 + ... + (N-1), which is O(N^2).

Space

O(N) to store the target array. If the space for the output is not considered, the space complexity is O(1).

Trade-offs

Pros

Works with a primitive array, avoiding the overhead of wrapper classes like Integer used in ArrayList.
Uses O(1) extra space if the output array is not counted as extra space.

Cons

The manual implementation of shifting elements is more verbose and prone to off-by-one errors compared to using a library class.
The code is less readable and less expressive of the high-level intent.

A more idiomatic and cleaner approach in Java is to use a dynamic array, such as ArrayList. The ArrayList class provides a convenient add(index, element) method that handles the underlying element shifting automatically. We can simply iterate through the input arrays and call this method to build the target list. Finally, we convert the ArrayList of Integer objects back to a primitive int[] array before returning.

Algorithm

Initialize an empty ArrayList<Integer> which will act as our target array.
Loop through the input arrays nums and index from i = 0 to nums.length - 1.
In each iteration, use the ArrayList.add(index, element) method to insert nums[i] at the position index[i].
After the loop, the ArrayList contains all the elements in the desired order.
Create a new primitive array int[] of the same size.
Copy the elements from the ArrayList to the int[] array.
Return the resulting int[] array.

Walkthrough

This method leverages Java's collections framework to simplify the implementation. We use an ArrayList because it's a resizable array that allows for efficient addition of elements at the end and provides a method for insertion at any arbitrary index. While insertion in the middle of an ArrayList is not an O(1) operation (it requires shifting subsequent elements), it abstracts away the manual shifting logic, leading to cleaner and more maintainable code.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] createTargetArray(int[] nums, int[] index) {6        // Use ArrayList for its dynamic size and convenient add(index, element) method.7        List<Integer> targetList = new ArrayList<>();8 9        for (int i = 0; i < nums.length; i++) {10            targetList.add(index[i], nums[i]);11        }12 13        // Convert the List<Integer> back to an int[] array for the result.14        int[] targetArray = new int[nums.length];15        for (int i = 0; i < targetList.size(); i++) {16            targetArray[i] = targetList.get(i);17        }18 19        return targetArray;20    }21}

Complexity

Time

O(N^2). The main loop runs N times. The `targetList.add(index[i], nums[i])` operation takes time proportional to the number of elements that need to be shifted, which is `list.size() - index[i]`. In the worst-case scenario (inserting at the beginning), this takes O(k) time at step `k`. The total time complexity is the sum of `k` for `k` from 0 to N-1, resulting in O(N^2).

Space

O(N) to store the elements in the `ArrayList`. An additional O(N) is required for the final `int[]` array.

Trade-offs

Pros

The code is simple, concise, and highly readable.
It directly maps the problem description to the ArrayList.add method, reducing the chance of implementation errors.
Leverages optimized native code (System.arraycopy) for shifting elements within the ArrayList.

Cons

Has the same quadratic time complexity as the manual shifting approach.
Incurs some overhead due to the use of the ArrayList class and Integer wrapper objects, though this is often negligible.

Solutions

Solution

1class Solution {2public3  int[] createTargetArray(int[] nums, int[] index) {4    int n = nums.length;5    List<Integer> target = new ArrayList<>();6    for (int i = 0; i < n; ++i) {7      target.add(index[i], nums[i]);8    }

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

1class Solution:2    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for x, i in zip(nums, index): target . insert(i, x) return target

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem