Skip to main content
Talentd

Create Target Array in the Given Order - Solution & Explanation

EasyArraySimulation14 min readAsked at: Amazon, Meta, Visa +2
Practice this problem

Problem Statement

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.

This solution defines a function createTargetArray which receives arrays nums and index, as well as a pre-allocated target array. For each element in nums, it shifts elements in target one position to the right from the index[i] position, making room for the new element. Then, it inserts the current element from nums into target at the index[i] position.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to the nested loop for shifting elements.
Space Complexity: O(1) since we use no extra data structures other than the target array which doesn't count towards extra space.

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.

This C solution leverages a linked list structure to handle insertions. The insert function allows for placing elements at any index without shifting other elements, which efficiently mimics inserting into dynamically positioned nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) as finding the insertion node requires linear traversal.
Space Complexity: O(n) for the linked list storage.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Basic Insertion with List/Array

Time Complexity: O(n^2) due to the nested loop for shifting elements.
Space Complexity: O(1) since we use no extra data structures other than the target array which doesn't count towards extra space.

Linked List Simulation

Time Complexity: O(n^2) as finding the insertion node requires linear traversal.
Space Complexity: O(n) for the linked list storage.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic Insertion with List/ArrayO(n^2)O(n)Best general solution. Simple simulation using built-in list insertion.
Linked List SimulationO(n^2)O(n)Useful when practicing linked list insertion and pointer manipulation.

Video Solution

1389 Create Target Array in the Given Order | Zero to FAANG Kunal | Assignment Solution | Leetcode • Programmers Zone • 9,943 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Create Target Array in the Given Order with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays