Python – Sort by Maximum digit in Element

Given a List of Elements, sort by the maximum digit of the element present in the List.

Input : test_list = [234, 92, 8, 721] 
Output : [234, 721, 8, 92] 
Explanation : 4 < 7 < 8 < 9, sorted by maximum digits.

Input : test_list = [92, 8, 721] 
Output : [721, 8, 92] 
Explanation : 7 < 8 < 9, sorted by maximum digits. 

Method #1 : Using max() + sort()

In this, we perform task of inplace sort using sort() and maximum element is extracted using max().

The original list is : [234, 92, 15, 8, 721]
Sorted List : [234, 15, 721, 8, 92]

Time Complexity: O(nlogn+m)
Auxiliary Space: O(1)

Method #2  : Using sorted() + lambda + max()

In this, we use sorted() perform non-inplace sort, and avoid usage of external function using lambda function to get maximum digit.

The original list is : [234, 92, 15, 8, 721]
Sorted List [234, 15, 721, 8, 92]

Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”.  sorted() + lambda + max() performs n*nlogn number of operations.
Auxiliary Space: O(1), no extra space is required 

Method #3  : Using a list comprehension with sorted():

1.Define the list of integers to be sorted.
2.Define a key function that takes an integer element and returns the maximum digit in the element.
3.Apply the sorted() function to the list, using the key function to determine the sorting order.
4.Print the resulting sorted list.

The original list is : [234, 92, 15, 8, 721]
[234, 15, 721, 8, 92]

Time complexity: O(d n log n), where d is the maximum number of digits in the list and n is the length of the list. In this case, the maximum number of digits is 3, since the maximum element is 721, which has 3 digits. Therefore, the time complexity is O(3 n log n), which simplifies to O(n log n).
Auxiliary space: O(n), since the key function creates a list of digits for each element and the sorted() function creates a new sorted list.

Method #5: Using a loop and a dictionary

Iterate through the list of numbers and for each number, you can extract the maximum digit and use it as a key to store the number in a dictionary. Finally, you can extract the numbers from the dictionary in ascending order of the maximum digit.

Step-by-step approach:

• Define an empty dictionary to store the numbers.
• Iterate through the list of numbers.
• For each number, convert it to a string and extract the maximum digit using the max() function.
• Check if the maximum digit already exists as a key in the dictionary. If it does, append the number to the list of numbers already stored under that key. If it doesn’t,
• Create a new key with the maximum digit and store the number as a list under that key.
• Extract the keys of the dictionary in ascending order.
• Iterate through the keys and extract the numbers stored under each key in the order they were added to the dictionary.
• Return the sorted list of numbers.

The original list is : [234, 92, 15, 8, 721]
Sorted List [234, 15, 721, 8, 92]

Time complexity: O(n log n), where n is the length of the list. 
Auxiliary space: O(n), where n is the length of the list. 

Method #7: Using itertools.groupby() and lambda function

• Import the itertools module.
• Define a lambda function to convert an integer to a list of its digits.
• Initialize a sorted() function that takes test_list as input and a key parameter that is set to the lambda function, which will sort the list by the maximum digit in each number.
• Use itertools.groupby() to group the sorted_list by their maximum digit.
• Extract the elements from each group and append them to a new list.
• Print the sorted list.

The original list is : [234, 92, 15, 8, 721]
Sorted List [234, 15, 721, 8, 92]

Time Complexity: O(n log n), where n is the length of test_list.
Auxiliary Space: O(n), where n is the length of test_list, due to the creation of the sorted_list and sorted_groups variables.