Domain 1EasyCORE

Create Target Array in the Given Order

The problem requires creating a target array by inserting elements from `nums` at positions specified by `index`. The target array starts empty, and we insert each element of `nums` into the target array at the position indicated by the corresponding element in `index`. The insertion operations are guaranteed to be valid.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1389. Create Target Array in the Given Order

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 84.9%


Problem Breakdown

The problem requires creating a target array by inserting elements from nums at positions specified by index. The target array starts empty, and we insert each element of nums into the target array at the position indicated by the corresponding element in index. The insertion operations are guaranteed to be valid.

Inputs:

  • Two arrays of integers: nums and index.
  • Lengths of both arrays are equal (1 <= nums.length, index.length <= 100).
  • Elements of nums range from 0 to 100.
  • Elements of index range from 0 to the current position in the target array.

Outputs:

  • A single array that is the result of inserting elements from nums into positions specified by index.

Implicit Constraints/Edge Cases:

  • The insertion operations are always valid, meaning no out-of-bounds errors will occur.
  • The arrays can be empty (though this is not explicitly stated in constraints).

Intuition

A brute-force approach would involve repeatedly inserting elements into a list at specific positions. This could be done using Python’s insert method, but it has a time complexity of O(n) for each insertion due to the need to shift elements. Given that we have up to 100 insertions, this could lead to a total time complexity of O(n^2), which is inefficient.

The key insight is to use a data structure that supports efficient insertions at arbitrary positions. A linked list would be suitable for this purpose because inserting into a linked list at any position has an average time complexity of O(1). However, since the problem constraints are small (n <= 100), and Python’s built-in list is optimized for such operations, we can use a list with slicing to achieve efficient insertions.

Approach

  1. Initialize an empty target array.
  2. Iterate through each element in nums and its corresponding position in index.
  3. For each element, insert it into the target array at the specified position using slicing.
  4. Return the final target array after all elements have been inserted.

Data Structure Choice:

  • We use a Python list to store the target array because it supports efficient insertion through slicing, and the constraints are small enough that this approach is optimal.

Complexity Analysis

  • Time Complexity: O(n^2) in the worst case due to the repeated insertions using slicing. However, given the constraint of n <= 100, this is acceptable.
  • Space Complexity: O(n) for storing the target array.

Solution

def createTargetArray(nums, index):
    target = []
    for i in range(len(nums)):
        target.insert(index[i], nums[i])
    return target

# Example usage:
print(createTargetArray([0,1,2,3,4], [0,1,2,2,1]))  # Output: [0,4,1,3,2]
print(createTargetArray([1,2,3,4,0], [0,1,2,3,0]))  # Output: [0,1,2,3,4]
print(createTargetArray([1], [0]))                  # Output: [1]

Edge Cases Handled

  • Empty Input: If both nums and index are empty, the function will return an empty list.
  • Single Element: If there is only one element in nums, it will be inserted at the position specified by index.
  • Insertions at the Beginning/End: The solution handles insertions at the start or end of the target array efficiently using slicing.