Problem Description

You are given two arrays: nums and index, both containing integers. Your task is to build a target array by following these steps:

1. Start with an empty target array
2. Read elements from both arrays simultaneously from left to right (reading nums[i] and index[i] together)
3. For each pair, insert the value nums[i] at position index[i] in the target array
4. Continue until all elements have been processed

The key point is that when you insert a value at a specific index, any existing elements at or after that position shift to the right to make room for the new element.

For example, if nums = [0,1,2,3,4] and index = [0,1,2,2,1]:

• Insert 0 at index 0: target = [0]
• Insert 1 at index 1: target = [0,1]
• Insert 2 at index 2: target = [0,1,2]
• Insert 3 at index 2: target = [0,1,3,2] (the 2 shifts right)
• Insert 4 at index 1: target = [0,4,1,3,2] (elements from index 1 onward shift right)

The solution uses Python's insert() method which handles the shifting automatically. The zip() function pairs up corresponding elements from nums and index arrays, and for each pair (x, i), it inserts value x at position i in the target array.

Intuition

The problem asks us to build an array by inserting elements at specific positions. The natural approach is to simulate exactly what the problem describes - start with an empty array and perform each insertion operation in order.

Since we need to process two arrays (nums and index) together where nums[i] tells us what value to insert and index[i] tells us where to insert it, we can pair these elements together. This naturally leads to using zip() to iterate through both arrays simultaneously.

The core insight is that we don't need any complex data structure or algorithm here. Python's list already provides an insert() method that does exactly what we need - it inserts an element at a given position and automatically shifts all subsequent elements to the right. This handles all the complexity of maintaining the correct order when inserting into the middle of the array.

Why does this straightforward simulation work? The problem guarantees that all insertion operations are valid, meaning we'll never try to insert at an invalid index. This allows us to directly use target.insert(i, x) without any bounds checking or special cases.

The time complexity might seem concerning since each insert() operation can take O(n) time in the worst case (when inserting at the beginning), but given the problem constraints and the guarantee of valid operations, this direct simulation is the most intuitive and clean solution.

Solution Approach

The solution uses a straightforward simulation approach to build the target array step by step.

Implementation Steps:

1. Initialize an empty list: We create an empty list called target that will store our result.

2. Iterate through paired elements: Using zip(nums, index), we pair up corresponding elements from both arrays. This gives us tuples like (nums[0], index[0]), (nums[1], index[1]), and so on.

3. Insert elements at specified positions: For each pair (x, i):

   • x is the value to insert (from nums)
   • i is the position where we insert it (from index)
   • We use target.insert(i, x) to insert value x at position i

4. Return the result: After processing all pairs, target contains the desired array.

How insert() works: When we call target.insert(i, x), Python:

• Places x at position i
• Shifts all elements from position i onwards to the right by one position
• This maintains the relative order of previously inserted elements

Example walkthrough with nums = [1,2,3], index = [0,1,0]:

• Start: target = []
• Insert 1 at index 0: target = [1]
• Insert 2 at index 1: target = [1, 2]
• Insert 3 at index 0: target = [3, 1, 2] (existing elements shift right)

The beauty of this approach is its simplicity - we let Python's built-in insert() method handle all the complexity of array manipulation, making the code clean and easy to understand.

Example Walkthrough

Let's trace through a small example with nums = [4, 2, 1, 3] and index = [0, 0, 1, 3].

Initial state: target = []

Step 1: Process (4, 0)

• Insert value 4 at index 0
• Since the array is empty, 4 becomes the first element
• target = [4]

Step 2: Process (2, 0)

• Insert value 2 at index 0
• The existing element 4 at index 0 shifts right to index 1
• target = [2, 4]

Step 3: Process (1, 1)

• Insert value 1 at index 1
• Element 4 at index 1 shifts right to index 2
• target = [2, 1, 4]

Step 4: Process (3, 3)

• Insert value 3 at index 3
• No shifting needed as we're appending at the end
• target = [2, 1, 4, 3]

The key observation is how insert() automatically handles the shifting. When we insert 2 at index 0 in Step 2, we don't manually move 4 - the insert() method takes care of this. Similarly, in Step 3, inserting at index 1 pushes everything from that position rightward.

This demonstrates why the simple approach of using target.insert(i, x) for each (x, i) pair from zip(nums, index) correctly builds our target array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code iterates through n elements using zip(nums, index), which takes O(n) time. For each element, it performs an insert() operation at position i in the target list. The insert() operation in Python lists has a time complexity of O(k) where k is the number of elements that need to be shifted to the right after the insertion point. In the worst case, when we always insert at the beginning (index 0), we need to shift all existing elements, leading to:

• 1st insertion: 0 shifts
• 2nd insertion: up to 1 shift
• 3rd insertion: up to 2 shifts
• ...
• nth insertion: up to n-1 shifts

This gives us a total of 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²) operations.

Space Complexity: O(n)

The code creates a target list that will eventually contain all n elements from the input. No additional data structures are used that scale with the input size. The space used by the target list is O(n), which dominates the space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Insert Behavior with Out-of-Bounds Indices

A common misconception is assuming that insert() will fail or behave unexpectedly when the index is greater than the current list length. In reality, Python's insert() method handles this gracefully by appending to the end of the list.

Example of the pitfall:

target = [1, 2, 3]
target.insert(10, 99)  # Index 10 is beyond list length
# Result: [1, 2, 3, 99] - Simply appends to the end

Why this matters: While the problem guarantees valid indices, understanding this behavior helps avoid confusion during debugging or when modifying the solution.

2. Performance Degradation with Large Arrays

The insert() operation has O(n) time complexity because it needs to shift elements. With n insertions, the overall time complexity becomes O(n²), which can be problematic for large inputs.

Alternative approach for better performance:

def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
    # For very large arrays, consider collecting operations first
    # then building the result more efficiently
    operations = list(zip(index, nums))
  
    # If performance is critical, could use a different data structure
    # like a linked list or deque for O(1) insertions
    from collections import deque
    target = deque()
    for pos, val in operations:
        # Convert to list for indexing, insert, then back to deque
        temp = list(target)
        temp.insert(pos, val)
        target = deque(temp)
    return list(target)

3. Assuming Index Values are Sorted

Developers might incorrectly assume that the index array values are in ascending order, leading to mental model errors when tracing through the algorithm.

Incorrect assumption example:

nums = [1, 2, 3]
index = [0, 1, 2]  # Might assume this is always the pattern

Reality - indices can be any valid position:

nums = [1, 2, 3]
index = [0, 0, 0]  # All insertions at position 0
# Result: [3, 2, 1] - Elements inserted in reverse order

4. Not Accounting for Index Shifting During Insertion

When manually tracing through the algorithm, it's easy to forget that each insertion affects the indices of subsequent elements.

Visualization of the mistake:

nums = [1, 2, 3]
index = [0, 1, 1]

# Incorrect mental model:
# "Insert 1 at position 0, 2 at position 1, 3 at position 1"
# Might think: [1, 3, 2] 

# Correct execution:
# Step 1: Insert 1 at 0 → [1]
# Step 2: Insert 2 at 1 → [1, 2]
# Step 3: Insert 3 at 1 → [1, 3, 2] (2 shifts right)

Solution: Always remember that insert() shifts existing elements at or after the insertion point to the right, changing their indices for future reference.