Python – Maximum of Similar Keys in Tuples

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.

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. 

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.

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)