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:
numsandindex. - Lengths of both arrays are equal (
1 <= nums.length, index.length <= 100). - Elements of
numsrange from0to100. - Elements of
indexrange from0to the current position in the target array.
Outputs:
- A single array that is the result of inserting elements from
numsinto positions specified byindex.
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
- Initialize an empty target array.
- Iterate through each element in
numsand its corresponding position inindex. - For each element, insert it into the target array at the specified position using slicing.
- 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
numsandindexare 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 byindex. - Insertions at the Beginning/End: The solution handles insertions at the start or end of the target array efficiently using slicing.