#1389

Easy

LeetCode Problem Workspace

Create Target Array in the Given Order

Learn how to efficiently create a target array by inserting elements at specified indices using array simulation techniques.

array simulation

Problem Statement

Given two integer arrays, nums and index, create a target array by inserting each nums[i] at position index[i]. Repeat this process for all elements in order, ensuring that existing elements shift right when necessary.

Return the resulting target array after all insertions. You may assume all insert operations are valid and arrays are of equal length.

Examples

Example 1

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]

Output: [0,4,1,3,2]

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]

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]

Example details omitted.

Constraints

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

Solution Approach

Iterative Simulation with Dynamic Array

Traverse nums and index simultaneously, inserting nums[i] at index[i] using the array's built-in insert method. This approach directly simulates the insertion process and maintains the correct ordering as required.

Optimized Using List Slicing

For each insertion, slice the target array into two parts, append nums[i] between them, and combine. This avoids shifting each element individually and can improve clarity, though it does not change time complexity.

Consider Using Linked List for Frequent Insertions

If the array is very large and insertions are frequent, a linked list can minimize element shifting. This aligns with the array plus simulation pattern by preserving insertion order efficiently at the cost of random access.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for array insertions due to shifting elements, while space complexity is O(n) for storing the target array.

What Interviewers Usually Probe

Look for correct handling of index-based insertions without overwriting existing elements.
Expect candidates to simulate array operations rather than attempting complex mathematical formulas.
Watch for off-by-one errors when elements need to shift to accommodate new insertions.

Common Pitfalls or Variants

Common pitfalls

Overwriting elements instead of shifting them during insertion.
Ignoring the correct order of operations, which can produce incorrect target arrays.
Assuming indexes are sorted or that insertions do not require dynamic adjustments.

Follow-up variants

Creating a target array with duplicate values in nums, testing stability of insertions.
Using extremely large arrays to explore time complexity limits of the simulation approach.
Modifying the problem to remove guarantees about valid insertions, requiring bounds checks.

FAQ

What is the best way to approach 'Create Target Array in the Given Order'?

Iterate through nums and index simultaneously, inserting each value at its corresponding position using array insert operations.

Why is this problem considered an array plus simulation pattern?

Because the solution involves simulating the insertion process step by step, updating the array dynamically as you go.

Can I use a linked list to solve this problem?

Yes, a linked list can reduce shifting cost for large arrays, but it may complicate random access compared to standard arrays.

What are common mistakes to avoid?

Overwriting elements instead of shifting, ignoring order of operations, and assuming indexes are pre-sorted.

What is the time complexity for this simulation approach?

O(n^2) due to repeated shifting of elements during insertions, with O(n) space to store the target array.

terminal

Solution

Solution 1: Simulation

We create a list $target$ to store the target array. Since the problem guarantees that the insertion position always exists, we can directly insert in the given order into the corresponding position.

1

2

3

4

5

6

class Solution:
    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

Continue Practicing

#1409 queries on a permutation with key #1441 build an array with stack operations #1324 print words vertically