Given two arrays of integers nums and index. Your task is to create target array under the following rules:
index[i] the value nums[i] in target array.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 <= 100nums.length == index.length0 <= nums[i] <= 1000 <= index[i] <= iProblem 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.
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.
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.
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.
Time Complexity: O(n^2) as finding the insertion node requires linear traversal.
Space Complexity: O(n) for the linked list storage.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Basic Insertion with List/Array | Time Complexity: O(n^2) due to the nested loop for shifting elements. |
| Linked List Simulation | Time Complexity: O(n^2) as finding the insertion node requires linear traversal. |
| Simulation | — |
| 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. |
1389 Create Target Array in the Given Order (Leetcode) | Easy Solution • PNT Coding • 6,580 views views
Watch 9 more video solutions →Practice Create Target Array in the Given Order with our built-in code editor and test cases.
Practice on FleetCode