Python | Element repetition in list

Sometimes we require to add a duplicate value in the list for several different utilities. This type of application is sometimes required in day-day programming. Let’s discuss certain ways in which we add a clone of a number to its next position. 

Method #1: Using list comprehension 

In this method, we just iterate the loop twice for each value and add it to the desired new list. This is just a shorthand alternative to the naive method. 

Output :

The original list is : [4, 5, 6, 3, 9]
The list after element duplication [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), since we are creating a new list with the duplicated elements.

Method #2 : Using reduce() + add We can also use the reduce function to act the function to perform the addition of a pair of similar numbers simultaneously in the list. 

Output :

The original list is : [4, 5, 6, 3, 9]
The list after element duplication [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time complexity: O(n).
Auxiliary space: O(n).

Method #3: Using itertools.chain().from_iterable() from_iterable function can also be used to perform this task of adding a duplicate. It just makes the pair of each iterated element and inserts it successively. 

Approach:

1. Initialize the original list test_list with some elements.
2. Print the original list using print().
3. Create a list comprehension that creates a list of duplicated elements for each element of the original list test_list.
4. Use itertools.chain.from_iterable() function to flatten the list of duplicated elements into a single list.
5. Convert the result to a list using list().
6. Print the result using print().

Output :

The original list is : [4, 5, 6, 3, 9]
The list after element duplication [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time complexity: O(n), where n is the length of the input list ‘test_list’.
Auxiliary space: O(n), as we are creating a new list ‘res’ of the same size as the input list ‘test_list’. The use of itertools.chain.from_iterable() function does not increase the space complexity as it creates an iterator and does not create a new list.

Method #4: Using repeat

You can use the repeat method of the itertools module to achieve the desired result of adding a duplicate element to the list. Here is how you can do it:

The original list is: [4, 5, 6, 3, 9]
The list after element duplication: [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time complexity: O(n)
Auxiliary Space: O(n)

Method #5:Using extend() method

Algorithm:

1. Initialize an empty list res.
2. Iterate through each element i in test_list.
3. Append i to res twice using the extend() method.
4. Return res after all elements have been processed.
5. Print the final result.

The original list is: [4, 5, 6, 3, 9]
The list after element duplication: [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time Complexity: O(n), where n is the number of elements in test_list. The algorithm iterates through each element in test_list exactly once.
Auxiliary Space: O(n), where n is the number of elements in test_list. The space used by res scales linearly with the size of test_list.

Method #6: Using slicing and concatenation

Approach:

• Create a new list res using list comprehension that contains duplicate elements of the original list. 
• For each element i in the original list test_list, create a new list that contains 2 copies of the element i.
  • Flatten the nested list of duplicate elements into a single list using another for loop and store it in the res variable.
• Print the resulting list using the print() function.

The original list is: [4, 5, 6, 3, 9]
The list after element duplication: [4, 4, 5, 5, 6, 6, 3, 3, 9, 9]

Time complexity: O(n), where n is the length of the list. This is because we only need to iterate over the list once to duplicate its elements.
Auxiliary space: O(n), where n is the length of the list. This is because we are creating a new list with the same length as the original list to store the duplicated elements.

Method #7: Using numpy:

Algorithm :

1. Initialize the input list test_list.
2. Print the original input list.
3. Use the np.repeat() method from NumPy to create a new array with duplicated elements.
4. Assign the result to the res variable.
5. Print the resulting list.

Output:
The original list is : [4, 5, 6, 3, 9]
The list after element duplication [4 4 5 5 6 6 3 3 9 9]

Time complexity: O(N)

The time complexity of the np.repeat() method is O(n) where n is the number of elements in the input list.
The print statements take constant time, so they don’t affect the overall time complexity.
Therefore, the time complexity of the code is O(n).

Auxiliary Space: O(N)

The space complexity of the code is O(n) because the res variable stores a new array with duplicate elements, which requires n*2 units of space.
The space complexity of the input list is also O(n).
Therefore, the total space complexity of the code is O(n).

Method #8: Using heapq module:

Algorithm :

1. Import the heapq module and initialize the test_list
2. Print the original test_list
3. Use the heapq.merge() method to merge the test_list with itself
4. Convert the result to a list using list()
5. Print the final result

The original list is: [4, 5, 6, 3, 9]
The list after element duplication: [4, 4, 5, 5, 6, 3, 6, 3, 9, 9]

Time complexity:
The time complexity of the code is O(n log n), where n is the length of the test_list. This is because the heapq.merge() method has a time complexity of O(n log n), and the list() method has a time complexity of O(n).

Space complexity:
The space complexity of the code is O(n), where n is the length of the test_list. This is because the heapq.merge() method returns an iterator, which does not create a new list in memory. Therefore, the space required is only for the new list created by the list() method.