Scale Engineer

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.

class Solution {    public int[] createTargetArray(int[] nums, int[] index) {        int n = nums.length;        int[] target = new int[n];        int size = 0; // current number of elements in target         for (int i = 0; i < n; i++) {            int idx = index[i];            int val = nums[i];             // Shift elements to the right to make space for the new element            // We shift elements from the current end (size-1) down to idx            for (int j = size; j > idx; j--) {                target[j] = target[j - 1];            }             // Insert the new element at the specified index            target[idx] = val;                        // Increment the size of the populated part of the array            size++;        }         return target;    }}

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.

Solutions

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

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 →

Next problem