LeetCode 1389 - Create Target Array in the Given Order

LeetCode Problem 1389

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

This problem asks us to build a new array called target by following a sequence of insertion operations. We are given two arrays, nums and index, where both arrays have the same length. At each position i, the value nums[i] must be inserted into the target array at position index[i].

The important detail is that insertion means placing the element at the specified position and shifting any existing elements to the right. This is different from assignment or replacement. If there are already elements at that index, they are not overwritten, instead they move one step to make room.

We process the arrays from left to right. Initially, target is empty. At every step, we read the pair (nums[i], index[i]), insert the number into the required position, and continue until all elements are processed.

The input consists of:

• nums, an integer array containing values to insert.
• index, an integer array containing insertion positions.

The expected output is the final target array after performing every insertion operation in order.

The constraints are relatively small:

• The length of both arrays is at most 100
• nums.length == index.length
• 0 <= index[i] <= i

The condition 0 <= index[i] <= i is extremely important because it guarantees every insertion is valid. At step i, the target array already contains exactly i elements, meaning an insertion index between 0 and i is always legal.

Because the input size is tiny, we do not need highly sophisticated optimizations. Even quadratic solutions are completely acceptable for n <= 100.

Several edge cases are worth noticing upfront. The smallest possible input contains only one element, which means the algorithm should correctly initialize and return a single-element array. Another important case occurs when insertions repeatedly happen at index 0, forcing all existing elements to shift right every time. Similarly, inserting at the current end position behaves like a normal append operation. The problem guarantees that invalid indices never occur, so we do not need bounds checking beyond standard insertion behavior.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to simulate the insertions manually using an array.

For each (nums[i], index[i]) pair, we create room at the desired position by shifting every element after index[i] one position to the right. Once space is available, we place nums[i] into the correct location.

This approach is correct because it directly follows the problem statement. Every insertion modifies the target array exactly as described.

However, shifting elements is expensive. In the worst case, if every insertion happens near the beginning of the array, we may shift nearly all existing elements for every operation. Since there are n insertions and each insertion may require up to O(n) shifts, the total time complexity becomes O(n²).

Optimal Approach

The key observation is that most programming languages already provide dynamic array insertion functionality.

Instead of manually shifting elements, we can simply maintain a growing target list and insert elements directly using built-in operations:

• In Python, use list.insert(index, value)
• In Go, use slice manipulation with append

Although insertion still internally shifts elements, this approach is simpler, cleaner, and perfectly efficient for the given constraints.

Since insertion into a dynamic array still requires shifting elements in the worst case, the time complexity remains O(n²). However, given that n <= 100, this is more than sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Manually shift elements for every insertion
Optimal	O(n²)	O(n)	Use dynamic array insertion operations

Algorithm Walkthrough

1. Initialize an empty array called target.
2. Iterate through both nums and index from left to right using the same index i. This order matters because the problem explicitly requires processing insertions sequentially.
3. At each step, retrieve:

• nums[i], the value to insert
• index[i], the position where it should be inserted

4. Insert nums[i] into target at position index[i]. Any elements already present at or after that position automatically shift one place to the right.
5. Continue until all elements have been processed.
6. Return the completed target array.

Why it works

The algorithm works because it exactly simulates the procedure described in the problem statement. After processing the first i elements, the target array always represents the correct intermediate state. Each insertion preserves the order established by previous operations while placing the new element at the required position. Since we process all insertions sequentially, the final result must match the intended target array.

Python Solution

from typing import List

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        target = []

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

        return target

The implementation begins by creating an empty list named target.

We then iterate through every index of nums and index. Since both arrays are guaranteed to have equal length, we can safely use the same loop index for both.

For every position i, we call target.insert(index[i], nums[i]). Python's insert method automatically places the element at the requested position and shifts existing elements to the right when necessary.

Finally, after all insertions are complete, we return target.

This implementation closely mirrors the algorithm and directly models the problem statement, making it easy to understand and verify.

Go Solution

func createTargetArray(nums []int, index []int) []int {
	target := make([]int, 0)

	for i := 0; i < len(nums); i++ {
		pos := index[i]

		target = append(target[:pos],
			append([]int{nums[i]}, target[pos:]...)...)
	}

	return target
}

The Go implementation uses slice operations because Go slices do not provide a built-in insertion method like Python lists.

To insert an element at position pos, we split the slice into two parts:

• target[:pos], elements before the insertion point
• target[pos:], elements at and after the insertion point

We then construct a new slice where nums[i] is placed between those two parts using append.

Unlike Python, Go requires explicit slice manipulation to simulate insertion behavior. Since integers in this problem are small and the array size is tiny, there are no concerns about integer overflow. Also, returning an empty slice versus nil does not matter here because the function always builds and returns a valid slice.

Worked Examples

Example 1

Input:

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

Step	nums[i]	index[i]	Target After Insertion
0	0	0	[0]
1	1	1	[0,1]
2	2	2	[0,1,2]
3	3	2	[0,1,3,2]
4	4	1	[0,4,1,3,2]

Final result:

[0,4,1,3,2]

At step 3, the insertion at index 2 shifts 2 to the right. At step 4, inserting 4 at index 1 shifts [1,3,2] rightward.

Example 2

Input:

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

Step	nums[i]	index[i]	Target After Insertion
0	1	0	[1]
1	2	1	[1,2]
2	3	2	[1,2,3]
3	4	3	[1,2,3,4]
4	0	0	[0,1,2,3,4]

Final result:

[0,1,2,3,4]

The last insertion demonstrates how inserting at index 0 pushes every existing element one position to the right.

Example 3

Input:

nums = [1]
index = [0]

Step	nums[i]	index[i]	Target After Insertion
0	1	0	[1]

Final result:

[1]

This example verifies that the algorithm works correctly for the minimum input size.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each insertion may shift up to n elements
Space	O(n)	The target array stores all n elements

The time complexity is O(n²) because inserting into the middle or front of an array requires shifting existing elements. In the worst case, every insertion happens at index 0, producing roughly 1 + 2 + ... + n operations.

The space complexity is O(n) because we store the resulting target array containing exactly n elements. No additional data structures proportional to input size are used.

Test Cases

class Solution:
    def createTargetArray(self, nums, index):
        target = []

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

        return target

solution = Solution()

# Example 1
assert solution.createTargetArray(
    [0, 1, 2, 3, 4],
    [0, 1, 2, 2, 1]
) == [0, 4, 1, 3, 2]  # standard example

# Example 2
assert solution.createTargetArray(
    [1, 2, 3, 4, 0],
    [0, 1, 2, 3, 0]
) == [0, 1, 2, 3, 4]  # insertion at front

# Example 3
assert solution.createTargetArray(
    [1],
    [0]
) == [1]  # minimum size input

# All insertions at front
assert solution.createTargetArray(
    [1, 2, 3, 4],
    [0, 0, 0, 0]
) == [4, 3, 2, 1]  # repeated shifting

# All append operations
assert solution.createTargetArray(
    [5, 6, 7],
    [0, 1, 2]
) == [5, 6, 7]  # behaves like append

# Mixed insertion positions
assert solution.createTargetArray(
    [10, 20, 30],
    [0, 1, 1]
) == [10, 30, 20]  # middle insertion

# Duplicate values
assert solution.createTargetArray(
    [1, 1, 1],
    [0, 1, 1]
) == [1, 1, 1]  # duplicates handled correctly

print("All tests passed!")

Test	Why
[0,1,2,3,4] with [0,1,2,2,1]	Verifies standard mixed insertion behavior
[1,2,3,4,0] with [0,1,2,3,0]	Tests insertion at front after several appends
[1] with [0]	Validates minimum input size
All indices 0	Ensures repeated front insertions work correctly
Sequential indices [0,1,2]	Confirms append-like behavior
Middle insertion case	Verifies shifting logic
Duplicate values	Ensures value uniqueness is not assumed

Edge Cases

Single Element Input

The smallest valid input contains only one number. A buggy implementation might accidentally mishandle initialization or return an empty result. Our implementation handles this naturally because the loop runs once and inserts the single value into an initially empty array.

Repeated Insertions at the Front

An input such as index = [0,0,0,0] forces every new element to be inserted at the beginning. This is a common source of bugs because existing elements must shift correctly every time. The built-in insertion logic in both Python and Go ensures the shifting is handled properly.

Insertions at the End

When index[i] == len(target), the operation behaves like appending to the array. Some implementations mistakenly treat insertion and append differently or introduce out-of-bounds errors. Since the problem guarantees valid indices, inserting at the current size is always safe, and both implementations support this case correctly.

Duplicate Numbers

The problem does not require values in nums to be unique. A flawed solution might accidentally rely on value uniqueness when manipulating positions. Our approach only depends on insertion order and indices, so duplicate values are handled without issue.