1389. Create Target Array in the Given Order Solution

Q: Is Create Target Array in the Given Order easy or hard?

Create Target Array in the Given Order is classified as an Easy problem. The challenge mainly tests basic array manipulation and understanding of insertion operations. No advanced algorithms are required, but careful simulation is necessary to maintain the correct order.

Q: Create Target Array in the Given Order Python/Java solution

In Python, use a list and call list.insert(index[i], nums[i]) while iterating through the arrays. In Java, use an ArrayList and call add(index[i], nums[i]). Both implementations simulate the required insert operations and run in O(n^2) time with O(n) space.

Q: How to solve Create Target Array in the Given Order in O(n)?

A strict O(n) solution is difficult with standard arrays because insertion requires shifting elements. Advanced data structures like balanced trees or indexed linked structures could reduce insertion cost, but they add unnecessary complexity. For the constraints of this problem, the O(n^2) simulation approach is the intended and accepted solution.

Q: What is the best approach for Create Target Array in the Given Order?

The most practical approach is simulating the insert operations using a dynamic array or list. Iterate through nums and insert each value at index[i] in the target list. Each insertion may shift elements, giving O(n^2) time complexity and O(n) space. This solution is simple and matches the problem statement directly.

Q: Is Create Target Array in the Given Order asked at Google/Amazon/Meta?

Problems focused on array simulation and insertion logic frequently appear in coding interviews at companies like Amazon and Google. While this exact problem may not always appear, the pattern of inserting elements at specific indices is a common interview concept used to test array manipulation skills.

Q: What data structure is used in Create Target Array in the Given Order?

The primary data structure is a dynamic array or list that supports insertion at arbitrary indices. Some implementations also use a linked list to practice pointer-based insertion. Both approaches simulate the same behavior but with different underlying structures.

Q: What is the time complexity of Create Target Array in the Given Order?

The typical simulation solution runs in O(n^2) time because inserting into the middle of an array shifts elements to the right. Since this shift can happen for every element, the total work becomes quadratic. Space complexity is O(n) for storing the resulting target array.

The problem

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

Initially target array is empty.
From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
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]
Explanation:
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]

Constraints:

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

Approach overview

Problem Overview: You receive two arrays: nums and index. For each position i, insert nums[i] into a target array at position index[i]. Elements already in the target array shift to the right. The final array after processing all insertions is the result.

Approach 1: Basic Insertion with List/Array (Simulation) (Time: O(n^2), Space: O(n))

Maintain a dynamic array (or list) called target. Iterate through nums and index simultaneously. For each step i, insert nums[i] at position index[i]. In most languages, inserting into the middle of an array shifts all elements to the right, which costs O(n). Since this operation may happen n times, the total time complexity becomes O(n^2) with O(n) extra space for the result.

This approach directly simulates the instructions in the problem statement, which makes it easy to implement and reason about. Standard list insertion operations in Python, Java ArrayList, or C++ vector handle the shifting automatically. Because the constraints for this problem are small, the quadratic time complexity is acceptable. This method primarily exercises concepts from Array manipulation and Simulation.

Approach 2: Linked List Simulation (Time: O(n^2), Space: O(n))

Instead of shifting elements in an array, maintain a linked list and insert nodes at the required positions. For each pair (nums[i], index[i]), traverse the linked list until you reach the node just before the target position, then update pointers to insert the new node. Insertion itself is O(1), but locating the correct position requires traversal, which costs O(n). Repeating this for all elements results in O(n^2) time and O(n) space.

This method models the shifting behavior of arrays using pointer manipulation. While it avoids physical element shifts, traversal still dominates the runtime. It is useful when practicing pointer-based operations with Linked List structures.

Recommended for interviews: The array/list insertion approach is what interviewers usually expect. It mirrors the problem statement exactly and demonstrates clear reasoning about array operations. Implementing the linked list variant shows deeper understanding of data structure tradeoffs, but the simple simulation with a dynamic array is the most practical solution.

Approach 1: Basic Insertion with List/Array

This approach uses a direct list or array insertion method to solve the problem. As we iterate through the arrays, nums and index, we insert nums[i] into the resulting target at the position defined by index[i]. This approach takes advantage of built-in list/array methods available in higher-level languages to perform this insertion directly.

Python

def create_target_array(nums, index):
    target = []
    for i, num in enumerate(nums):
        target.insert(index[i], num)
    return target

nums = [0, 1, 2, 3, 4]
index = [0, 1, 2, 2, 1]
target = create_target_array(nums, index)
print(target)

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> targetList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            targetList.add(index[i], nums[i]);
        }
        int[] target = new int[nums.length];
        for (int i = 0; i < target.length; i++) {
            target[i] = targetList.get(i);
        }
        return target;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0, 1, 2, 3, 4};
        int[] index = {0, 1, 2, 2, 1};
        int[] target = solution.createTargetArray(nums, index);
        for (int t : target) {
            System.out.print(t + " ");
        }
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
    vector<int> target;
    for (int i = 0; i < nums.size(); i++) {
        target.insert(target.begin() + index[i], nums[i]);
    }
    return target;
}

int main() {
    vector<int> nums = {0, 1, 2, 3, 4};
    vector<int> index = {0, 1, 2, 2, 1};
    vector<int> target = createTargetArray(nums, index);
    for (int t : target) {
        cout << t << " ";
    }
    return 0;
}

JavaScript

function createTargetArray(nums, index) {
    let target = [];
    for (let i = 0; i < nums.length; i++) {
        target.splice(index[i], 0, nums[i]);
    }
    return target;
}

const nums = [0, 1, 2, 3, 4];
const index = [0, 1, 2, 2, 1];
const target = createTargetArray(nums, index);
console.log(target);

#include <stdio.h>
#include <stdlib.h>

void createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* target) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = numsSize-1; j > index[i]; j--) {
            target[j] = target[j-1];
        }
        target[index[i]] = nums[i];
    }
}

int main() {
    int nums[] = {0, 1, 2, 3, 4};
    int index[] = {0, 1, 2, 2, 1};
    int numsSize = 5;
    int target[5];
    createTargetArray(nums, numsSize, index, numsSize, target);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", target[i]);
    }
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static int[] CreateTargetArray(int[] nums, int[] index) {
        List<int> targetList = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            targetList.Insert(index[i], nums[i]);
        }
        return targetList.ToArray();
    }

    static void Main(string[] args) {
        int[] nums = {0, 1, 2, 3, 4};
        int[] index = {0, 1, 2, 2, 1};
        int[] target = CreateTargetArray(nums, index);
        Console.WriteLine(string.Join(" ", target));
    }
}

Python's built-in list method insert() simplifies the process. We iterate through nums[i], inserting each element at the specified index[i] into target. This insertion causes elements at and beyond index[i] to shift right.

Complexity

Time Complexity: O(n^2) as each insert operation can lead to shifting elements.
Space Complexity: O(n) for the target list.

Try this approach in the editor

Approach 2: Linked List Simulation

This alternative approach simulates linked list behavior to achieve efficient insertions. By maintaining linked nodes and inserting at the specified index, we avoid the full array shifts seen in a typical list/array implementation.

Python

from collections import deque

def create_target_array(nums, index):
    target = deque()
    for i, num in enumerate(nums):
        target.insert(index[i], num)
    return list(target)

nums = [0, 1, 2, 3, 4]
index = [0, 1, 2, 2, 1]
target = create_target_array(nums, index)
print(target)

Java

import java.util.LinkedList;

public class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        LinkedList<Integer> targetList = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            targetList.add(index[i], nums[i]);
        }
        int[] target = new int[nums.length];
        for (int i = 0; i < target.length; i++) {
            target[i] = targetList.get(i);
        }
        return target;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0, 1, 2, 3, 4};
        int[] index = {0, 1, 2, 2, 1};
        int[] target = solution.createTargetArray(nums, index);
        for (int t : target) {
            System.out.print(t + " ");
        }
    }
}

C++

#include <iostream>
#include <list>
using namespace std;

list<int> createTargetArray(int* nums, int* index, int size) {
    list<int> targetList;
    for (int i = 0; i < size; i++) {
        auto it = targetList.begin();
        advance(it, index[i]);
        targetList.insert(it, nums[i]);
    }
    return targetList;
}

int main() {
    int nums[5] = {0, 1, 2, 3, 4};
    int index[5] = {0, 1, 2, 2, 1};
    list<int> targetList = createTargetArray(nums, index, 5);
    for (int t : targetList) {
        cout << t << " ";
    }
    return 0;
}

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    insert(index, value) {
        const newNode = new Node(value);
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            for (let i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
    }

    toArray() {
        const result = [];
        let current = this.head;
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        return result;
    }
}

function createTargetArray(nums, index) {
    const linkedList = new LinkedList();
    for (let i = 0; i < nums.length; i++) {
        linkedList.insert(index[i], nums[i]);
    }
    return linkedList.toArray();
}

const nums = [0, 1, 2, 3, 4];
const index = [0, 1, 2, 2, 1];
const target = createTargetArray(nums, index);
console.log(target);

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void insert(struct Node** head, int index, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (index == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 0; i < index - 1; i++) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

int* createTargetArray(int* nums, int numsSize, int* index, int indexSize) {
    struct Node* head = NULL;
    for (int i = 0; i < numsSize; i++) {
        insert(&head, index[i], nums[i]);
    }
    int* result = (int*)malloc(numsSize * sizeof(int));
    struct Node* temp = head;
    for (int i = 0; i < numsSize; i++) {
        result[i] = temp->data;
        temp = temp->next;
    }
    return result;
}

int main() {
    int nums[] = {0, 1, 2, 3, 4};
    int index[] = {0, 1, 2, 2, 1};
    int numsSize = 5;
    int* target = createTargetArray(nums, numsSize, index, numsSize);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", target[i]);
    }
    free(target);
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static int[] CreateTargetArray(int[] nums, int[] index) {
        LinkedList<int> targetList = new LinkedList<int>();
        for (int i = 0; i < nums.Length; i++) {
            if (index[i] == 0) {
                targetList.AddFirst(nums[i]);
            } else {
                LinkedListNode<int> current = targetList.First;
                for (int j = 0; j < index[i] - 1; j++) {
                    current = current.Next;
                }
                targetList.AddAfter(current, nums[i]);
            }
        }
        int[] target = new int[nums.Length];
        int k = 0;
        foreach (int val in targetList) {
            target[k++] = val;
        }
        return target;
    }

    static void Main(string[] args) {
        int[] nums = {0, 1, 2, 3, 4};
        int[] index = {0, 1, 2, 2, 1};
        int[] target = CreateTargetArray(nums, index);
        Console.WriteLine(string.Join(" ", target));
    }
}

Python's collections.deque mimics linked list behavior with efficient pre-append operations. Using insert on deque simplifies manipulation similar to linked nodes, capturing the element dynamics desired.

Complexity

Time Complexity: O(n^2) as insert in deque is not optimized for every situation
Space Complexity: O(n) as deques store elements adjacent to simulate linked nodes.

Try this approach in the editor

Approach 3: 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.

The time complexity is O(n^2), and the space complexity is O(n). Where n is the length of the array.

TypeScript

function createTargetArray(nums: number[], index: number[]): number[] {
    const ans: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        ans.splice(index[i], 0, nums[i]);
    }
    return ans;
}

func createTargetArray(nums []int, index []int) []int {
	target := make([]int, len(nums))
	for i, x := range nums {
		copy(target[index[i]+1:], target[index[i]:])
		target[index[i]] = x
	}
	return target
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Basic Insertion with List/Array	Time Complexity: O(n^2) as each insert operation can lead to shifting elements. Space Complexity: O(n) for the target list.
Linked List Simulation	Time Complexity: O(n^2) as `insert` in `deque` is not optimized for every situation Space Complexity: O(n) as deques store elements adjacent to simulate linked nodes.
Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Basic Insertion with List/Array	O(n^2)	O(n)	Best general solution. Simple simulation using built-in list insertion.
Linked List Simulation	O(n^2)	O(n)	Useful when practicing linked list insertion and pointer manipulation.

Frequently asked questions

Is Create Target Array in the Given Order easy or hard?

Create Target Array in the Given Order is classified as an Easy problem. The challenge mainly tests basic array manipulation and understanding of insertion operations. No advanced algorithms are required, but careful simulation is necessary to maintain the correct order.

Create Target Array in the Given Order Python/Java solution

In Python, use a list and call list.insert(index[i], nums[i]) while iterating through the arrays. In Java, use an ArrayList and call add(index[i], nums[i]). Both implementations simulate the required insert operations and run in O(n^2) time with O(n) space.

How to solve Create Target Array in the Given Order in O(n)?

A strict O(n) solution is difficult with standard arrays because insertion requires shifting elements. Advanced data structures like balanced trees or indexed linked structures could reduce insertion cost, but they add unnecessary complexity. For the constraints of this problem, the O(n^2) simulation approach is the intended and accepted solution.

What is the best approach for Create Target Array in the Given Order?

The most practical approach is simulating the insert operations using a dynamic array or list. Iterate through nums and insert each value at index[i] in the target list. Each insertion may shift elements, giving O(n^2) time complexity and O(n) space. This solution is simple and matches the problem statement directly.

Is Create Target Array in the Given Order asked at Google/Amazon/Meta?

Problems focused on array simulation and insertion logic frequently appear in coding interviews at companies like Amazon and Google. While this exact problem may not always appear, the pattern of inserting elements at specific indices is a common interview concept used to test array manipulation skills.

What data structure is used in Create Target Array in the Given Order?

The primary data structure is a dynamic array or list that supports insertion at arbitrary indices. Some implementations also use a linked list to practice pointer-based insertion. Both approaches simulate the same behavior but with different underlying structures.

What is the time complexity of Create Target Array in the Given Order?

The typical simulation solution runs in O(n^2) time because inserting into the middle of an array shifts elements to the right. Since this shift can happen for every element, the total work becomes quadratic. Space complexity is O(n) for storing the resulting target array.

Create Target Array in the Given Order solution and explanation

The problem

Approach overview

Approach 1: Basic Insertion with List/Array

Approach 2: Linked List Simulation

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Create Target Array in the Given Order solution and explanation

The problem

Approach overview

Approach 1: Basic Insertion with List/Array

Approach 2: Linked List Simulation

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems