The flattening of list of list has been discussed many times, but sometimes, in addition to flattening, it is also required to get the string in reverse sorted manner. Let’s discuss certain ways in which this can be done.
Method #1: Using sorted() + reverse + list comprehension This idea is similar to flattening a list of list but in addition to it, we add a sorted function along with reverse as key, to reverse sort the returned flattened list done by list comprehension.
Python3
# Python3 code to demonstrate# Flatten and Reverse Sort Matrix# using sorted + list comprehension# initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]# printing original list of listprint("The original list : " + str(test_list))# using sorted + list comprehension# Flatten and Reverse Sort Matrixres = sorted([j for i in test_list for j in i], reverse=True)# print resultprint("The reverse sorted and flattened list : " + str(res)) |
The original list : [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list : [12, 9, 7, 5, 3, 3, 1]
Time Complexity: O(nlogn), where n is the length of the input list. This is because we’re using the sorted() + reverse + list comprehension which has a time complexity of O(nlogn) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.
Method #2: Using itertools.chain() + sorted() + reverse The task that was done by list comprehension above can also be performed using the chain function that links elements of list and then sorted function does the task of sorting with the help of reverse for reverse sorting.
Python3
# Python3 code to demonstrate# Flatten and Reverse Sort Matrix# using itertools.chain() + sorted()from itertools import chain# initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]# printing original list of listprint("The original list : " + str(test_list))# using itertools.chain() + sorted()# Flatten and Reverse Sort Matrixres = sorted(chain(*test_list), reverse=True)# print resultprint("The reverse sorted and flattened list : " + str(res)) |
The original list : [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list : [12, 9, 7, 5, 3, 3, 1]
Time Complexity: O(n*nlogn), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.
Method #3 : Using extend() and sort() methods
Python3
# Python3 code to demonstrate# Flatten and Reverse Sort Matrix# initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]# printing original list of listprint("The original list : " + str(test_list))# using sorted + list comprehension# Flatten and Reverse Sort Matrixres=[]for i in test_list: res.extend(i)res.sort(reverse=True) # print resultprint("The reverse sorted and flattened list : " + str(res)) |
The original list : [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list : [12, 9, 7, 5, 3, 3, 1]
Time Complexity: O(nlogn), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.
Method #4: Using recursion
Python3
def flatten(lst): if not lst: return [] if isinstance(lst[0], list): return flatten(lst[0]) + flatten(lst[1:]) return lst[:1] + flatten(lst[1:])#initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]#printing original list of listprint("The original list : " + str(test_list))#using recursionres = sorted(flatten(test_list), reverse=True)#print resultprint("The reverse sorted and flattened list : " + str(res))#This code is contributed by Edula Vinay Kumar Reddy |
The original list : [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list : [12, 9, 7, 5, 3, 3, 1]
Time complexity : O(n log n)
Auxiliary Space: O(n)
Method 5: Use a stack and a while loop.
Step-by-step approach:
- Initialize an empty list flat_list to store the flattened list.
- Initialize a stack stack with the input list lst.
- Use a while loop to iterate through the stack until it becomes empty.
- Pop the last element from the stack and check if it is a list or not using isinstance() function. If it is a list, extend the stack with its elements in reverse order. If it is not a list, append it to flat_list.
- Use sorted() function with the reverse=True parameter to sort the flat_list in reverse order.
- Return the sorted flattened list.
Python3
def flatten(lst): flat_list = [] stack = [lst] while stack: item = stack.pop() if isinstance(item, list): stack.extend(item[::-1]) else: flat_list.append(item) return sorted(flat_list, reverse=True)# Initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]# Printing original list of listprint("The original list : " + str(test_list))# Using stack and while loopres = flatten(test_list)# Printing resultprint("The reverse sorted and flattened list : " + str(res)) |
The original list : [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list : [12, 9, 7, 5, 3, 3, 1]
Time complexity: O(n log n), where n is the total number of elements in the input list lst. The sorted() function takes O(n log n) time to sort the flattened list in reverse order.
Auxiliary space: O(n), where n is the total number of elements in the input list lst.
Method 6: Using a generator function and heapq
Python3
import heapqdef flatten_and_sort(lst): def flatten_generator(lst): for item in lst: if isinstance(item, list): yield from flatten_generator(item) else: yield item flat_list = list(flatten_generator(lst)) heapq.heapify(flat_list) sorted_list = [] while flat_list: sorted_list.append(heapq.heappop(flat_list)) return sorted_list[::-1]# Initializing list of listtest_list = [[3, 5], [7, 3, 9], [1, 12]]# Printing original list of listprint("The original list: " + str(test_list))# Using generator function and heapqres = flatten_and_sort(test_list)# Printing resultprint("The reverse sorted and flattened list: " + str(res)) |
The original list: [[3, 5], [7, 3, 9], [1, 12]] The reverse sorted and flattened list: [12, 9, 7, 5, 3, 3, 1]
Time complexity is O(n + n + n log n) = O(n log n).
The auxiliary space is O(n) because we create a flat list to store all the elements before sorting them.
