Python | Combine two lists by maintaining duplicates in first list
Given two lists, the task is to combine two lists and removing duplicates, without removing duplicates in original list.
Example:
Input : list_1 = [11, 22, 22, 15] list_2 = [22, 15, 77, 9] Output : OutList = [11, 22, 22, 15, 77, 9]
Code #1: using extend
Python3
# Python code to combine two lists # and removing duplicates, without # removing duplicates in original list. # Initialisation of first list list1 = [ 111 , 222 , 222 , 115 ] # Initialisation of Second list list2 = [ 222 , 115 , 77 , 19 ] output = list (list1) # Using extend function output.extend(y for y in list2 if y not in output) # printing result print (output) |
[111, 222, 222, 115, 77, 19]
Time complexity: O(n^2) as it uses nested loop to check each element of list2 with the elements of output list.
Auxiliary space: O(n) as it uses a separate list to store the combined elements without duplicates.
Code #2 : Using Set and Iteration Append those element in first list which are not in second list and then take union of first and second list.
Python3
# Python code to combine two lists # and removing duplicates, without # removing duplicates in original list. # Initialisation of first list list1 = [ 11 , 22 , 22 , 15 ] # Initialisation of Second list list2 = [ 22 , 15 , 77 , 9 ] # creating set unique_list1 = set (list1) unique_list2 = set (list2) # Difference in two sets diff_element = unique_list2 - unique_list1 # union of difference + first list output = list1 + list (diff_element) # printing output print (output) |
[11, 22, 22, 15, 9, 77]
Time complexity: O(n*n) as it uses nested loop to check each element of list2 with the elements of output list.
Auxiliary space: O(n) as it uses a separate list to store the combined elements without duplicates.
Code #3 : Using collectionss
This version first creates a Counter object for each of the lists, just like before. Then, it adds the two Counter objects using the + operator, but it only includes the elements from list2 that are not in list1. This is achieved using a generator expression that filters the elements in counter2 based on whether they are not in counter1. Finally, it converts the combined Counter object to a list using the elements() method, just like before.
Python3
from collections import Counter # Initialize the lists list1 = [ 11 , 22 , 22 , 15 ] list2 = [ 22 , 15 , 77 , 9 ] # Create a Counter object for each list counter1 = Counter(list1) counter2 = Counter(list2) # Add the Counter objects, but only add the elements from list2 that are not in list1 combined_counter = counter1 + Counter(el for el in counter2 if el not in counter1) # Convert the combined Counter object to a list output = list (combined_counter.elements()) # Print the output print (output) #This code is contributed by Edula Vinay Kumar Reddy |
[11, 22, 22, 15, 77, 9]
Time complexity: O(n), where n is the total number of elements in the two lists. This is because the Counter class uses a dictionary data structure to store the elements and their counts, and the time complexity of the Counter operations (e.g. creating a Counter object, adding two Counter objects, and converting a Counter object to a list) is O(1) on average.
Auxiliary space: O(n), because the combined Counter object will store a count for each element in the two lists, and the resulting list will contain all the elements from the two lists.
Method 4: Using loop + append()
Uses a for loop to iterate over the elements of the second list, and then it checks if each element is already present in the output list using the not in operator. If it’s not present, it appends it to the output list using the append() method. This approach essentially builds a new list that combines the elements of both input lists while removing duplicates, without modifying the original lists. This approach is similar to the original program, but it explicitly makes a copy of the first list before iterating over the second list.
- Define two input lists list1 and list2 with some initial values.
- Create a copy of list1 using the list() constructor and assign it to a new list variable called output.
- Use a for loop to iterate over the elements of list2. For each element y:
- Check if y is already present in output using the not in operator.
- If y is not present in output, append it to output using the append() method.
- Print the resulting list output.
Implementation:
Python3
# Python code to combine two lists # and removing duplicates, without # removing duplicates in original list. # Initialisation of first list list1 = [ 111 , 222 , 222 , 115 ] # Initialisation of Second list list2 = [ 222 , 115 , 77 , 19 ] # Make a copy of list1 to avoid modifying the original list output = list (list1) # Iterate over the elements of list2 and append them to the output list # only if they are not already present in it for y in list2: if y not in output: output.append(y) # Print the resulting list print (output) |
[111, 222, 222, 115, 77, 19]
Time Complexity: O(m*n), where m and n are the lengths of the two input lists list1 and list2
Auxiliary Space: O(m + n)
Using numpy:
Note: Install numpy module using command “pip install numpy”
Approach:
In this approach, we will use the numpy.setdiff1d function to find the unique elements of arr2 that are not present in arr1. We will then convert the resulting array to a list and append it to list1.
Algorithm:
Import numpy library.
Define list1 and arr2 with some initial values.
Use np.setdiff1d function to find unique elements of arr2 that are not in arr1 and assign the result to arr2_unique.
Convert arr2_unique to a list using the tolist() method and append it to list1.
Print the resulting list.
Python3
import numpy as np # Define input lists list1 = [ 11 , 22 , 22 , 15 ] arr2 = np.array([ 22 , 15 , 77 , 9 ]) # Find unique elements of arr2 that are not in list1 arr2_unique = np.setdiff1d(arr2, list1, assume_unique = True ) # Append arr2_unique to list1 result_list = list1 + arr2_unique.tolist() # Print the resulting list print (result_list) |
Output:
[11, 22, 22, 15, 77, 9]
Time complexity:
Creating a NumPy array takes O(n) time where n is the length of the input list.
np.setdiff1d function takes O(n*log(n)) time for sorting and finding the unique elements.
tolist() method takes O(n) time to convert the NumPy array to a list.
Appending two lists takes O(n) time where n is the total length of the lists.
Therefore, the overall time complexity of this approach is O(n*log(n)).
Auxiliary Space:
Creating a NumPy array takes O(n) space where n is the length of the input list.
The arr2_unique array created by np.setdiff1d function takes O(m) space where m is the number of unique elements in arr2 that are not in list1.
The result_list list takes O(n+m) space to store the combined elements of list1 and arr2_unique.
Therefore, the overall space complexity of this approach is O(n+m).
Contact Us