# Create Target Array in the Given Order **Difficulty:** EASY [External](https://leetcode.com/problems/create-target-array-in-the-given-order) Canonical: https://scaleengineer.com/dsa/problems/create-target-array-in-the-given-order **Data structures:** Array **Companies:** [Visa](https://scaleengineer.com/companies/visa) --- ## 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` # Approaches ## Brute Force with Manual Array Shifting This approach directly simulates the insertion process using a standard fixed-size array. Since inserting into the middle of a primitive array is not a built-in operation, we must manually implement the logic to shift elements to the right to create a space for each new element. We iterate through the given `nums` and `index` arrays, and for each pair, we perform the shift-and-insert operation on our `target` array. **Time:** O(N^2), where N is the number of elements. The outer loop runs N times. In each iteration `i`, the inner loop for shifting can run up to `i` times in the worst case (when `index[i]` is 0). The total number of operations is proportional to the sum 1 + 2 + ... + (N-1), which is O(N^2). · **Space:** O(N) to store the target array. If the space for the output is not considered, the space complexity is O(1). **Pros:** Works with a primitive array, avoiding the overhead of wrapper classes like `Integer` used in `ArrayList`.; Uses O(1) extra space if the output array is not counted as extra space. **Cons:** The manual implementation of shifting elements is more verbose and prone to off-by-one errors compared to using a library class.; The code is less readable and less expressive of the high-level intent. ### Explanation We initialize a `target` array with the final required size. We also use a `size` variable to track how many elements have been inserted so far. For each element `nums[i]` to be inserted at `index[i]`, we first shift all elements from `index[i]` up to the current end of the populated part of the array (`size - 1`) one step to the right. This opens up a spot at `index[i]`, where we can then place `nums[i]`. This process is repeated for all elements. ```java class Solution { public int[] createTargetArray(int[] nums, int[] index) { int n = nums.length; int[] target = new int[n]; int size = 0; // current number of elements in target for (int i = 0; i < n; i++) { int idx = index[i]; int val = nums[i]; // Shift elements to the right to make space for the new element // We shift elements from the current end (size-1) down to idx for (int j = size; j > idx; j--) { target[j] = target[j - 1]; } // Insert the new element at the specified index target[idx] = val; // Increment the size of the populated part of the array size++; } return target; } } ``` ### Algorithm - Create a result array `target` of size `n`, where `n` is the length of the input arrays. - Initialize a variable `size` to 0, which will keep track of the number of elements currently in the `target` array. - Iterate through the input arrays from `i = 0` to `n-1`: - Get the value `nums[i]` and the insertion index `index[i]`. - To make space for the new element at `index[i]`, shift all elements from that index to the current end of the array (`size - 1`) one position to the right. This must be done in reverse order (from right to left) to avoid overwriting data. - Insert `nums[i]` at `index[i]`. - Increment the `size` of the array. - After the loop completes, return the `target` array. ## Simulation using Dynamic Array (ArrayList) A more idiomatic and cleaner approach in Java is to use a dynamic array, such as `ArrayList`. The `ArrayList` class provides a convenient `add(index, element)` method that handles the underlying element shifting automatically. We can simply iterate through the input arrays and call this method to build the target list. Finally, we convert the `ArrayList` of `Integer` objects back to a primitive `int[]` array before returning. **Time:** O(N^2). The main loop runs N times. The `targetList.add(index[i], nums[i])` operation takes time proportional to the number of elements that need to be shifted, which is `list.size() - index[i]`. In the worst-case scenario (inserting at the beginning), this takes O(k) time at step `k`. The total time complexity is the sum of `k` for `k` from 0 to N-1, resulting in O(N^2). · **Space:** O(N) to store the elements in the `ArrayList`. An additional O(N) is required for the final `int[]` array. **Pros:** The code is simple, concise, and highly readable.; It directly maps the problem description to the `ArrayList.add` method, reducing the chance of implementation errors.; Leverages optimized native code (`System.arraycopy`) for shifting elements within the `ArrayList`. **Cons:** Has the same quadratic time complexity as the manual shifting approach.; Incurs some overhead due to the use of the `ArrayList` class and `Integer` wrapper objects, though this is often negligible. ### Explanation This method leverages Java's collections framework to simplify the implementation. We use an `ArrayList` because it's a resizable array that allows for efficient addition of elements at the end and provides a method for insertion at any arbitrary index. While insertion in the middle of an `ArrayList` is not an O(1) operation (it requires shifting subsequent elements), it abstracts away the manual shifting logic, leading to cleaner and more maintainable code. ```java import java.util.ArrayList; import java.util.List; class Solution { public int[] createTargetArray(int[] nums, int[] index) { // Use ArrayList for its dynamic size and convenient add(index, element) method. List targetList = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { targetList.add(index[i], nums[i]); } // Convert the List back to an int[] array for the result. int[] targetArray = new int[nums.length]; for (int i = 0; i < targetList.size(); i++) { targetArray[i] = targetList.get(i); } return targetArray; } } ``` ### Algorithm - Initialize an empty `ArrayList` which will act as our `target` array. - Loop through the input arrays `nums` and `index` from `i = 0` to `nums.length - 1`. - In each iteration, use the `ArrayList.add(index, element)` method to insert `nums[i]` at the position `index[i]`. - After the loop, the `ArrayList` contains all the elements in the desired order. - Create a new primitive array `int[]` of the same size. - Copy the elements from the `ArrayList` to the `int[]` array. - Return the resulting `int[]` array. # Solutions ### Java ```java class Solution { public int[] createTargetArray(int[] nums, int[] index) { int n = nums.length; List target = new ArrayList<>(); for (int i = 0; i < n; ++i) { target.add(index[i], nums[i]); } ``` ### CPP ```cpp class Solution { public: vector createTargetArray(vector &nums, vector &index) { vector target; for (int i = 0; i < nums.size(); ++i) { target.insert(target.begin() + index[i], nums[i]); } return target; } }; ``` ### Python ```python class Solution: def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for x, i in zip(nums, index): target . insert(i, x) return target ```