1389. Create Target Array in the Given Order

EasyArraySimulation

Problem Description

The problem gives us two arrays: nums and index. The goal is to construct a new array called target. To create this target array, we need to follow specific rules:

Start with an empty target array.
Read elements from nums and index arrays from left to right. For each pair (nums[i], index[i]), insert the value nums[i] into the target array at the position specified by index[i].
Keep inserting elements into the target array until there are no more elements to read from nums and index.

The challenge requires us to return this target array after all insertions are complete. It is guaranteed in the problem statement that the insertion operations, as described by the index array, will be valid—which means they won't lead to any out-of-bounds errors.

Intuition

The intuition behind the solution is straightforward, as the problem specifies the exact steps needed to arrive at the target array. With each pair of elements from nums and index, we directly follow the rule and use the insert operation.

Here's the intuitive approach step-by-step:

Start with an empty list for the target.
Loop over nums and index using the zip() function in Python, which conveniently gives us pairs of (nums[i], index[i]).
For each pair, use the insert() method on the target list, which allows us to place elements not just at the end of the list (like append) but at any position we specify.
The iteration continues until every element from nums has been placed into the target at the correct positions.
Finally, return the target array, which now contains all the elements from nums sorted by the rules of the index array.

This solution is elegant due to Python's list handling capabilities and delivers the expected target array using a direct translation of the problem's rules into code.

Solution Approach

The implementation of the solution is straightforward and follows the problem description closely. It utilizes the built-in list data structure in Python and the insert() method it provides. The solution does not rely on any sophisticated algorithms or complex patterns; rather, it uses a basic iterative approach that corresponds with the rules defined in the problem.

Here's the detailed implementation description:

Start by initializing an empty list target that will eventually hold the final array.
Use the built-in Python function zip() to iterate over both the nums and index arrays simultaneously. zip(nums, index) creates an iterator of tuples where the first item in each passed iterator is paired together, then the second item, and so on. In this case, it pairs each element in nums with its corresponding element in index.
For each pair (x, i) obtained from zipping nums and index, perform an insert operation: target.insert(i, x). This line is the core of the solution, where i is the position in the target array where we want to insert the element, and x is the actual element from nums we want to insert.
The insert() method takes two arguments: the first argument is the index at which to insert the item, and the second argument is the item to insert. It modifies the list in place, which means no new list is created, the existing target list is updated.
This process is repeated until there are no more elements to read, meaning every element from nums has been placed into the target list in the order specified by index.
Return the target list.

By utilizing the insert() method, we can insert elements at specific positions, which provides a seamless way to construct the target array. The solution follows the insertion rules exactly as specified and the simplicity of the approach reflects the clarity of the problem’s instructions. It is worth noting that while insert() operation is efficient for small to medium-sized lists, inserting elements into a list has a time complexity of O(n) per operation because it may require shifting over other elements. However, for the constraints of this problem, the approach is suitable and efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the following small example to illustrate the solution approach:

Suppose nums = [0, 1, 2, 3, 4] and index = [0, 1, 2, 2, 1].

Following the algorithm:

Initialize the target list as empty: target = [].
Now begin iterating over the nums and index arrays simultaneously.
- First pair: (0, 0) - insert 0 at index 0 of target → target = [0].
- Second pair: (1, 1) - insert 1 at index 1 of target → target = [0, 1].
- Third pair: (2, 2) - insert 2 at index 2 of target → target = [0, 1, 2].
- Fourth pair: (3, 2) - insert 3 at index 2 of target. This will push the current element at index 2 (which is 2) to the right → target = [0, 1, 3, 2].
- Fifth pair: (4, 1) - insert 4 at index 1 of target. This will push elements starting from index 1 to the right → target = [0, 4, 1, 3, 2].
At this point, we have read all elements from nums and index, and the target list is fully constructed.
The final step is to return the target list which is [0, 4, 1, 3, 2].

This example clearly demonstrates how elements from the nums array are inserted into the target array at the positions dictated by the corresponding index values. Each insert operation respects the current state of the target array, potentially shifting elements to make room for the new ones. The final target array reflects the ordered insertions as per the given nums and index arrays.

Solution Implementation

1from typing import List  # Importing List from typing module for type hints
2
3class Solution:
4    def createTargetArray(self, nums: List[int], indices: List[int]) -> List[int]:
5        # Initialize an empty target array
6        target = []
7      
8        # Loop over the pairs of elements from nums and their corresponding indices
9        for num, idx in zip(nums, indices):
10            # Insert the element 'num' at the index 'idx' of the target array
11            target.insert(idx, num)
12      
13        # Return the final target array
14        return target
15

1class Solution {
2    public int[] createTargetArray(int[] nums, int[] index) {
3        // Get the length of the input array.
4        int n = nums.length;
5        // Initialize an ArrayList to hold the target elements.
6        List<Integer> targetList = new ArrayList<>();
7        // Iterate through each element of nums and index arrays.
8        for (int i = 0; i < n; ++i) {
9            // Add the current element from nums into the targetList at the position given by index[i].
10            targetList.add(index[i], nums[i]);
11        }
12
13        // Initialize the target array.
14        int[] targetArray = new int[n];
15        // Convert the ArrayList back into an array.
16        for (int i = 0; i < n; ++i) {
17            targetArray[i] = targetList.get(i);
18        }
19        // Return the resultant target array.
20        return targetArray;
21    }
22}
23

1#include <vector>   // Include vector header for std::vector
2using namespace std;
3
4class Solution {
5public:
6    /**
7     * Create a target array by inserting elements from the 'nums' array into the
8     * 'target' array at positions specified by the 'index' array.
9     * 
10     * @param nums A vector of integers to insert into the target array.
11     * @param index A vector of integers indicating the indices at which
12     *              to insert the elements from the nums vector.
13     * @return The target vector after all insertions.
14     */
15    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
16        vector<int> target; // The target vector that we'll return
17      
18        // Iterate over all elements in 'nums' and 'index'
19        for (int i = 0; i < nums.size(); ++i) {
20            // At the position index[i], insert the value nums[i] into the 'target' vector
21            target.insert(target.begin() + index[i], nums[i]);
22        }
23
24        return target; // Return the completed target vector
25    }
26};
27

1// Function to create a target array according to the specified order
2function createTargetArray(nums: number[], indices: number[]): number[] {
3    // Initialize the target array to hold the result
4    const targetArray: number[] = [];
5
6    // Iterate over the nums array to populate the target array
7    for (let i = 0; i < nums.length; i++) {
8        // Insert the current number at the specified index in the target array
9        // The splice method modifies the array in place and can insert elements
10        targetArray.splice(indices[i], 0, nums[i]);
11    }
12
13    // Return the resulting target array after the loop completes
14    return targetArray;
15}
16

Time and Space Complexity

Time Complexity

The given code has a time complexity of O(n^2). This is because for each element x in nums, the method insert() is called which can take O(n) time in the worst case, as it requires shifting all the elements after the inserted element by one position to make space for the new element. Since there are n insert operations, and each might take up to O(n) time, the overall time complexity is O(n * n), which simplifies to O(n^2).

Space Complexity

The space complexity of the code is O(n). The target list that is created, in the worst case, will contain all the elements from the nums list, thus the amount of space used grows linearly with the input size n. No additional space other than the target list (which is the desired output) is used, hence the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: