Create Target Array in the Given Order - Video Solutions
1389 Create Target Array in the Given Order | Zero to FAANG Kunal | Assignment Solution | Leetcode
Create Target Array in the Given Order - Video Solution
Watch 10 video solutions for Create Target Array in the Given Order, a easy level problem involving Array, Simulation. This walkthrough by Programmers Zone has 9,943 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 valuenums[i]in target array. - Repeat the previous step until there are no elements to read in
numsandindex.
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] <= 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.
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. |