Python | Sort Flatten list of list
Last Updated :
08 May, 2023
The flattening of list of lists has been discussed earlier, but sometimes, in addition to flattening, it is also required to get the string in a sorted manner. Let’s discuss certain ways in which this can be done.
Method #1 : Using sorted() + list comprehension This idea is similar to flattening a list of list but in addition to it, we add a sorted function to sort the returned flattened list done by list comprehension.
Python3
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
res = sorted([j for i in test_list for j in i])
print("The sorted and flattened list : " + str(res))
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list : [1, 3, 3, 5, 7, 9, 12]
Time Complexity: O(n log n) where n is the total number of elements in the nested list.
Auxiliary Space: O(n)
Method #2 : Using itertools.chain() + sorted() 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.
Python3
from itertools import chain
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
res = sorted(chain(*test_list))
print("The sorted and flattened list : " + str(res))
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list : [1, 3, 3, 5, 7, 9, 12]
The time complexity of the provided code is O(nlogn), where n is the total number of elements in the input list of lists.
The auxiliary space complexity of the code is O(n), where n is the total number of elements in the input list of lists.
Method #3: Using the sorted function and the sum function:
Here is another approach using the sorted function and the sum function:
Python3
test_list = [[3, 5], [7, 3, 9], [1, 12]]
result = sorted(sum(test_list, []))
print("Original list:", test_list)
print("Flattened and sorted list:", result)
|
Output
Original list: [[3, 5], [7, 3, 9], [1, 12]]
Flattened and sorted list: [1, 3, 3, 5, 7, 9, 12]
This code first uses the sum function to concatenate the lists in test_list and pass an empty list as the initial value. This results in a new list that is the concatenation of the lists in test_list. Then, the sorted function is used to sort the resulting list.
In terms of time complexity, this code has a complexity of O(n * log(n)) since it needs to concatenate the lists in test_list and then sort the resulting list, which both have a complexity of O(n). In terms of space complexity, it has a complexity of O(n) since it creates a new list that is the concatenation of the lists in test_list.
Method #4 : Using sort() and extend() methods
Python3
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
res=[]
for i in test_list:
res.extend(i)
res.sort()
print("The sorted and flattened list : " + str(res))
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list : [1, 3, 3, 5, 7, 9, 12]
Time Complexity : O(N*logN)
Auxiliary Space : O(1)
Method #5 : Using a nested for loop:
Python3
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
res = []
for sub_list in test_list:
for item in sub_list:
res.append(item)
res.sort()
print("The sorted and flattened list : " + str(res))
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list : [1, 3, 3, 5, 7, 9, 12]
Time Complexity: O(N log n)
Auxiliary Space: O(N)
Method#6 : Using reduce and operator.add
Python3
import functools
import operator
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
flattened_list = functools.reduce(operator.add, test_list)
sorted_list = sorted(flattened_list)
print("The sorted and flattened list:", sorted_list)
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list: [1, 3, 3, 5, 7, 9, 12]
Time Complexity: O(N log N)
Auxiliary Space: O(N)
Method#7: Using Recursive method.
Python3
def flatten_and_sort(lst):
flat_list = []
for i in lst:
if type(i) == list:
flat_list.extend(flatten_and_sort(i))
else:
flat_list.append(i)
return sorted(flat_list)
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("The original list : " + str(test_list))
res = flatten_and_sort(test_list)
print("The sorted and flattened list : " + str(res))
|
Output
The original list : [[3, 5], [7, 3, 9], [1, 12]]
The sorted and flattened list : [1, 3, 3, 5, 7, 9, 12]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method # 8 : Using a stack
- Create an empty stack and push the input list onto it.
- Create an empty list to store the flattened list.
- While the stack is not empty, pop the top element from the stack.
- If the popped element is a list, then push its elements onto the stack.
- If the popped element is not a list, then append it to the flattened list.
- Sort the flattened list using the sorted() function.
Python3
def flatten_and_sort(lst):
stack = [lst]
flat_list = []
while stack:
element = stack.pop()
if isinstance(element, list):
stack.extend(element)
else:
flat_list.append(element)
return sorted(flat_list)
test_list = [[3, 5], [7, 3, 9], [1, 12]]
print("Original list:", test_list)
result = flatten_and_sort(test_list)
print("Flattened and sorted list:", result)
|
Output
Original list: [[3, 5], [7, 3, 9], [1, 12]]
Flattened and sorted list: [1, 3, 3, 5, 7, 9, 12]
Time complexity: O(n log n) for the sort operation, where n is the total number of elements in the list of lists.
Auxiliary space: O(n), where n is the total number of elements in the list of lists, for the stack and flattened list.
Please Login to comment...