Python Beginner Algorithms Tutorial

Create Target Array in the Given Order (via Leetcode)

This problem can be found on Leetcode.

Problem statement:

Given two arrays of integers, nums and index, create a target array. From examination of the input arrays from left to right, insert nums[i] at index[i] in the target array.

It is guaranteed that the insertion operations will be valid.

Test Cases

In [10]:
# assert create_target_array(nums=[0, 1, 2, 3, 5], index=[0, 1, 2, 2, 1]) == [0, 5, 1, 3, 2]

Explanation of how target_list is created upon iteration of nums and index.

nums index target_list
0 0 [0]
1 1 [0, 1]
2 2 [0, 1, 2]
3 2 [0, 1, 3, 2]
4 1 [0, 5, 1, 3, 2]
In [11]:
# assert create_target_array(nums=[5, 7, 9, 10], index=[0, 1, 2, 0]) == [10, 5, 7, 9]

Explanation of how target_list is created upon iteration of nums and index.

nums index target
5 0 [5]
7 1 [5, 7]
9 2 [5, 7, 9]
10 0 [10, 5, 7, 9]

Pseudocode

In [12]:
# define a function that takes in an input list:
    # create empty target list
    # iterate over nums and index at the same time using zip function
        # insert num in target list at index 
    # return target list

Code

In [13]:
def create_target_array(nums, index):
    target_list = []
    for num, ind in zip(nums, index):
        target_list.insert(ind, num)
    return target_list

Complexity

Let n be the count of values in nums which is equivalent to the count of values in index too.

Time complexity is O(n) because there is one iteration over the indices of nums and index at the same time.

Space complexity is O(n) because target_list is created that has a length of n.

Verify Code with Test Cases

In [14]:
assert create_target_array(nums=[0, 1, 2, 3, 5], index=[0, 1, 2, 2, 1]) == [0, 5, 1, 3, 2]
In [15]:
assert create_target_array(nums=[5, 7, 9, 10], index=[0, 1, 2, 0]) == [10, 5, 7, 9]