Watch 10 video solutions for Create Target Array in the Given Order, a easy level problem involving Array, Simulation. This walkthrough by PNT Coding has 6,580 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |