Python | Insert Nth element to Kth element in other list

Sometimes, while working with Python list, there can be a problem in which we need to perform the inter-list shifts of elements. Having a solution to this problem is always very useful. Let’s discuss the certain way in which this task can be performed. 

Method 1: Using pop() + insert() + index()

This particular task can be performed using a combination of the above functions. In this, we just use the property of pop function to return and remove the element and insert it to the specific position of the other list using the index function. 

The original list 1 is : [4, 5, 6, 7, 3, 8]
The original list 2 is : [7, 6, 3, 8, 10, 12]
The list 1 after insert is : [4, 5, 6, 12, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

Time Complexity: O(n), n is the length of the list.
Auxiliary Space: O(1)

Method 2: Using slicing and concatenation

This approach involves slicing the original list1 into two parts, the first part contains the elements before the Kth position, and the second part contains the elements after the Kth position. Then, we concatenate the first part, the Nth element of list2, and the second part using the + operator to form a new list. Finally, we print the updated list1 and the remaining elements of list2.

Approach:

1. Creates a new list res by taking a slice of test_list1 from the beginning up to the Kth element (exclusive), concatenating it with a list containing the Nth element of test_list2, and concatenating that with a slice of test_list1 from the Kth element to the end. This effectively inserts the Nth element of test_list2 into the Kth position of test_list1.
2. Prints the resulting list res using the print() function.
3. The program creates a new list by taking a slice of test_list2 from the beginning up to the Nth element (exclusive), concatenating it with a slice of test_list2 from the N+1th element to the end. This effectively removes the Nth element from test_list2.
4. Prints the resulting list using the print() function.

Below is the implementation of the above approach:

The list 1 after insert is : [4, 5, 6, 12, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

Time complexity: O(n), where n is the length of the lists.
Auxiliary space: O(n), where n is the length of the lists.

Method 3:  using list comprehension

 Here’s a step-by-step approach:

1. Initialize two lists test_list1 and test_list2:
2. Initialize two variables N and K:
3. Use list comprehension to create a new list res that contains the first K elements of test_list1, the element from test_list2 at index N, and the remaining elements of test_list1:
4. Print the updated lists:

The list 1 after insert is : [4, 5, 6, 12, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

Time complexity: O(n), where n is the length of the lists.
Auxiliary space: O(n) as well, since we are creating a new list.

Method#4: Using the Recursive method

In this recursive method, we use two input lists test_list1 and test_list2, an integer N indicating the index of the element to remove from test_list2, and an integer K indicating the index of the element in test_list1 to insert before the N-th element of test_list2.

In the base case, when N is 0, we return a new list with the first element of test_list2 followed by all the elements of test_list1.

In the recursive case, we first check if K is 0. If it is, we return a new list with the N-th element of test_list2 followed by the result of recursively calling insert_remove with test_list1 and test_list2 but with N decreased by 1 and K set to 0.

If K is not 0, we return a new list with the first element of test_list1 followed by the result of recursively calling insert_remove with the rest of test_list1, the same test_list2, the same N, and K decreased by 1.

Finally, we can call the insert_remove function with the input lists and indices to get the result. Note that this implementation assumes that K and N are valid indices for the input lists, and does not perform any input validation or error checking.

The list 1 after insert is : [4, 5, 6, 12, 10, 8, 3, 6, 7, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

The time complexity of the recursive method is O(N+K) where N is the length of test_list2 and K is the position of the element to be inserted in test_list1. This is because each recursive call either decreases N or K by 1 until we reach the base case where N is 0.

The space complexity of the recursive method is O(N+K) as well since each recursive call creates a new list with a total of N+K elements. However, since Python has a recursion limit, the maximum depth of the recursion is limited by the system and may cause a runtime error if the limit is exceeded.

Method #5: Using the extend() method

Here’s the step-by-step approach:

1. Initialize two lists: test_list1 and test_list2.
2. Print the original lists using the print() function.
3. Initialize two variables: N and K.
4. Use the extend() method to insert the Nth element from test_list2 into test_list1 at the K^th position.
5. Print the updated test_list1 and test_list2 using the print() function.

The original list 1 is : [4, 5, 6, 7, 3, 8]
The original list 2 is : [7, 6, 3, 8, 10, 12]
The list 1 after insert is : [4, 5, 6, 12, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

Time Complexity: O(n), where n is the length of test_list2. 
Auxiliary Space: O(1), as we are only using a constant amount of extra memory for the variables N and K.

Method #6: Using the itertools module

This approach involves using the itertools.chain() function to concatenate the first K elements of test_list1, the (N-K) elements of test_list2 before the Nth element, the Nth element of test_list2, and the remaining elements of test_list1:

• Import the itertools module.
• Use the chain() function to concatenate the following four iterators:
  • The first K elements of test_list1, obtained using slicing.
  • The (N-K) elements of test_list2 before the Nth element, obtained using slicing.
  • The Nth element of test_list2, obtained using indexing.
  • The remaining elements of test_list1, obtained using slicing.
• Convert the iterator returned by chain() into a list using the list() function.
• Assign the resulting list to a variable called res.

The list 1 after insert is : [4, 5, 6, 8, 10, 12, 7, 3, 8]
The list 2 after remove is : [7, 6, 3, 8, 10]

Time complexity: O(N+K), where N is the length of test_list2 and K is the length of test_list1 up to the Kth element.
Auxiliary space: O(N+K)