A Guide to Flatten List & List of Lists in Python

By | June 11, 2021

Python List is one of the widely used Python data containers. The list can store multiple data objects. It can store any type of Python data object including itself. A list containing a list is known as a multi-dimensional list, it could be 2D, 3d, or multi-d. Often in Python interviews, the developer asks to flatten a Python list, in which we have given a list of lists and we need to convert it into a linear or 1-D list.

For Example 

Vamware
Input:
[[10, 20, 30, 40], [50, 60,70], [80, 90], [100, 110]]
Output:
[10, 20, 30, 40, 50 ,60, 70, 80, 90, 100, 110]

In this Python tutorial, we will discuss this Python problem and learn how can we flatten a Python 2-D and Multi-D List into a 1-D list.

How to Convert a 2D Python list to a 1D list?

A 2D list is a list of 1D list. And converting a 2D list to a 1D list is very straightforward, and there are two techniques we can use to achieve our goal.

  1. Using Loop
  2. Using Itertools chain

1. Using Loops

The most common way to flatten a 2D list to a 1D list is by using for loops. In this approach, we use for loop and iter over every list element present in the main list and store them in a new flatten list.

Algorithm

  1. Initialize an empty list one_d that will store all the elements of the 2D list in linear order.
  2.  Loop through every element of 2D list and extend it to the one_d list.
  3. The Python list’s extend method to append all the iterable elements to the end of the list.
  4. At last return the 1D array

Example

def flat_2d(two_d):
    # initialize a new empty list
    # that will contain all the list elements in 1-D pattern
    one_d = []

    for i in two_d:
        # extend list elements to one_d list
        one_d.extend(i)

    return one_d

two_d = [[10, 20, 30, 40], [50, 60,70], [80, 90], [100, 110]]

print(flat_2d(two_d))

Output

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]

Complexity analysis

Time Complexity: The time complexity of the above program is O(N^2) because we are using the extend method inside the for loop and the time complexity of Extend method itself is O(N), so the overall time complexity of the above program is O(N^2).

Space Complexity: As we are using an extra empty list, which makes the space complexity of the above program O(N)

Where N is the total number of elements present in the List.

In the above program instead of extend method we could have used the nested for loop with the append method.

Example

def flat_2d(two_d):
    # initialize a new empty list
    # that will contain all the list elements in 1-D pattern
    one_d = []

    for i in two_d:
        # for nested list elements
        for j in i:
            #add element to the 1D list
            one_d.append(j)

    return one_d

two_d = [[10, 20, 30, 40], [50, 60,70], [80, 90], [100, 110]]

print(flat_2d(two_d))

2. Using Itertools chain

Python provides a built itertoolsmodule that deals with different Python iterators. The itertools module supports a chain() function that can accept a series of iterable and return a single iterable.

We can use the itertools chain() function to convert our 2D list to a 1D list.

Syntax

itertools.chain(*iterable)

Example

import itertools

def flat_2d(two_d):
    # flat the 2D list to 1D
    one_d = list( itertools.chain(*two_d))

    return one_d

two_d = [[10, 20, 30, 40], [50, 60,70], [80, 90], [100, 110]]

print(flat_2d(two_d))

Output

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]

The inner working of chain() function is very similar to the nested for loop algorithm that we discussed in the above section so the time complexity of chain() function is also O(N^2), And it can only flat 2D Python list.

How to Convert a Mult-level or Multi-D Python list to a 1D list

In the above section, we discuss two different approaches to convert or flatten a Python 2D list to a 1D list. Both the above approaches can only work when the list is 2D if the list has multiple levels or even contain single elements, then both the above approaches may show some error or unwanted result.

But in interviews, the interviewer may ask you to convert a multi-level list to a 1D list, there you can not use the for loops or itertools chain() function, because there we are not certain about the depth of the nested lists. In that case, we have to write some logic that can dive deep into every list element and check if the element is a list or a single element.

Example

Input
[10,[20,30,40] ,[50, 60, [70, 80]], 90, [[100,110], [120,130]]] Output [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130]

To flatten a multi-level or Multi-D Python list we have to use recursion.

In recursion, we keep calling the function again and again until a base condition gets satisfied. To know more about Python recursion click here.

# initialize a 1D list that will store all the
# multi-D elements in single order
one_d =[]

def flat_multi(multi):
    # iterate over every element of multi-d list
    for element in multi:
        # check if the element is a list
        # then call flat_multi() function
        # recursivly for that list
        if type(element)==list:
            # recursive call
            flat_multi(element)
        # if the element is not a list
        # append the element to the one_d list
        else:
            one_d.append(element)

multi = [10,[20,30,40] ,[50, 60, [70, 80]], 90, [[100,110], [120,130]]]

# flat the multi level array
flat_multi(multi)

# print the 1D list
print(one_d)

Output

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130]

Break the code

In the above program, we first initialize an empty array one_d that is supposed to store all the elements like a 1D list.

In the flat_multi() function, we create a for loop that iterates over every element of the multilist and recursively calls the flat_multi() function if the element is a list. Else it appends the single element to the one_dlist. With this when we call the flat_multi() function, it appends all the single integer elements to the one_d list.

Wrapping Up!

In this Python tutorial, we learned how to flatten a Python list. By flattening a list we mean converting a 2D or multi-level list to a 1D list. The most efficient way to flatten a list is recursion, however, we can also use nested for loop or itertools chain() function to convert a 2D list to a 1D list. In interviews, if the interviewer asks you to flatten a list try to use the recursion method.

 

Leave a Reply

Your email address will not be published. Required fields are marked *