Create Target Array in the Given Order (via Leetcode)¶

Date published: 2020-04-13

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, lists

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]

# 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]

# 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

# 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

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]

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]

assert create_target_array(nums=[5, 7, 9, 10], index=[0, 1, 2, 0]) == [10, 5, 7, 9]