Sometimes, while working with Python tuples, we can have a problem in which we need to perform maximum of all values of the equal keys in Tuple list. This kind of application in useful in many domains such as web development and day-day programming. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [(4, 8), (4, 2), (4, 2), (4, 6)]
Output : [(4, 8)]Input : test_list = [(1, 8), (2, 2), (3, 6), (4, 2)]
Output : [(1, 8), (2, 2), (3, 6), (4, 2)]
Method #1 : Using max() + groupby() + lambda + loop
The combination of above functions can be used to solve this problem. In this, we perform the task of grouping using groupby() and maximum is extracted using max(), and result is compiled using loop.
Python3
# Python3 code to demonstrate working of # Maximum of Similar Keys in Tuples# Using max() + groupby() + lambda + loopfrom itertools import groupby# initializing liststest_list = [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)]# printing original listprint("The original list is : " + str(test_list))# Maximum of Similar Keys in Tuples# Using max() + groupby() + lambda + looptest_list.sort(key = lambda sub: sub[0]) temp = groupby(test_list, lambda ele: ele[0])res = []for key, val in temp: res.append((key, sum([ele[1] for ele in val])))# printing result print("Maximum grouped elements : " + str(res)) |
The original list is : [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)] Maximum grouped elements : [(2, 2), (3, 7), (4, 8)]
Time complexity: O(nlogn) where n is the number of tuples in the list, because sorting the list takes O(nlogn) time.
Auxiliary space: O(n) where n is the number of tuples in the list, because res list with n elements is created.
Method #2 : Using max() + groupby() + itemgetter() + list comprehension
The combination of above functions can be used to solve this problem. In this, we perform similar task as above, the second element is chosen using itemgetter and list comprehension is used to compile elements and extract result.
Python3
# Python3 code to demonstrate working of # Maximum of Similar Keys in Tuples# Using max() + groupby() + itemgetter() + list comprehensionfrom itertools import groupbyfrom operator import itemgetter# initializing liststest_list = [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)]# printing original listprint("The original list is : " + str(test_list))# Maximum of Similar Keys in Tuples# Using max() + groupby() + itemgetter() + list comprehensiontemp = groupby(sorted(test_list, key = itemgetter(0)), key = itemgetter(0))res = [(key, max(map(itemgetter(1), sub))) for key, sub in temp]# printing result print("Maximum grouped elements : " + str(res)) |
The original list is : [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)] Maximum grouped elements : [(2, 2), (3, 7), (4, 8)]
Time complexity: O(nlogn) – sorting the list takes nlogn time, where n is the length of the input list. The groupby function also takes linear time, but the max and map functions inside the list comprehension are negligible compared to the other operations.
Auxiliary space: O(n) – creating the sorted list and the groupby object requires additional memory proportional to the length of the input list. However, the space used by the result list is also proportional to n, so the overall space complexity is O(n).
Method #3 : Using Counter and list comprehension:
Algorithm:
1.Create a Counter object from the given list of tuples.
2.Convert the Counter object into a dictionary.
3.Sort the keys of the dictionary.
4.Create a list of tuples from the sorted dictionary, where each tuple contains the key and its corresponding value.
Python3
from collections import Counter# initializing liststest_list = [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)] # printing original listprint("The original list is : " + str(test_list))# using Counter to count the frequency of each keyd = dict(Counter(dict(test_list)))# creating a list of tuples sorted by keyres = [(k, d[k]) for k in sorted(d)]# printing resultprint("Maximum grouped elements : " + str(res))#This code is contributed by Jyothi pinjala. |
The original list is : [(4, 8), (3, 2), (2, 2), (4, 6), (3, 7), (4, 5)] Maximum grouped elements : [(2, 2), (3, 7), (4, 5)]
Time complexity: O(nlogn) (due to sorting of dictionary keys)
Auxiliary Space: O(n) (to store the Counter and dictionary objects)
