Given two list of tuples, write a Python program to update ‘list1’ according to the ‘list2’ and return an updated list.
Examples:
Input : list1 = [('x', 0), ('y', 5)]
list2 = [('x', 100), ('y', 200)]
Output : [('x', 100), ('y', 200)]
Input : list1 = [('a', 0), ('b', 0), ('c', 0)]
list2 = [('a', 1), ('b', 2)]
Output :[('a', 1), ('b', 2), ('c', 0)]
Approach #1 Pythonic Naive This is a Pythonic naive approach. We simply convert the list of tuples into a dictionary and just update it with list2 and convert the dictionary back to list.
Python3
# Python3 code to Update a list # of tuples according to another listdef merge(list1, list2): dic = dict(list1) dic.update(dict(list2)) return list(dic.items())# Driver Codelist1 = [('a', 0), ('b', 0), ('c', 0)]list2 = [('a', 5), ('c', 3)]print(merge(list1, list2)) |
[('a', 5), ('b', 0), ('c', 3)]
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.
Approach #2 Using defaultdict Python collections module provides defaultdict() method which is used in this approach. First we initialize ‘dic’ with defaultdict method passing list as factory. Use a loop to append the left element of each tuple as key and right element of each tuple as value for both the lists. Now simply use the sorted function and produce the list in such a way that the for each unique key it keeps the maximum value of right element of tuple.
Python3
# Python3 code to Update a list # of tuples according to another listfrom collections import defaultdictdef merge(list1, list2): dic = defaultdict(list) for i, j in list1 + list2: dic[i].append(j) return sorted([(i, max(j)) for i, j in dic.items()], key = lambda x:x[0])# Driver Codelist1 = [('a', 0), ('b', 0), ('c', 0)]list2 = [('a', 5), ('c', 3)]print(merge(list1, list2)) |
[('a', 5), ('b', 0), ('c', 3)]
Approach #3: Using simple iteration:
Python3
def merge(list1, list2): dic = {} for key, value in list1 + list2: dic[key] = value return list(dic.items())list1 = [('x', 0), ('y', 5)]list2 = [('x', 100), ('y', 200)]print(merge(list1, list2)) # [('a', 5), ('b', 0), ('c', 3#This code is contributed by Edula Vinay Kumar Reddy |
[('x', 100), ('y', 200)]
This code defines a function merge that takes in two lists of tuples list1 and list2. The function creates an empty dictionary dic. It then iterates over the tuples in list1 and list2 and adds them to the dictionary dic as key-value pairs. The function then returns a list of tuples representing the key-value pairs in the dictionary dic.
The time complexity of this code is O(n) where n is the total number of tuples in list1 and list2. This is because the function iterates over each tuple in the lists once. The space complexity of this code is also O(n) as the dictionary dic will store n key-value pairs.
When the code is run with the given input, it will print [(‘x’, 100), (‘y’, 200)].
Approach#4: Using list
this approach uses a list comprehension to iterate through list2 and either replace the value in list1 if the key exists or append the key-value tuple to list1 if the key does not exist.
Algorithm
1. Iterate through list2 and check if the key exists in list1.
2. If the key exists, replace the value in list1.
3. If the key does not exist, append the key-value tuple to list1.
4. Return list1.
Python3
def update_list_of_tuples_using_list_comprehension(list1, list2): for key, value in list2: for i in range(len(list1)): if list1[i][0] == key: list1[i] = (key, value) break else: list1.append((key, value)) return list1list1 = [('x', 0), ('y', 5)]list2 = [('x', 100), ('y', 200)]print(update_list_of_tuples_using_list_comprehension(list1, list2)) |
[('x', 100), ('y', 200)]
Time Complexity: O(n*m) where n is the length of list1 and m is the length of list2.
Space Complexity: O(1)
