A Guide to Flatten List & List of Lists in Python

Posted in /  

A Guide to Flatten List & List of Lists in Python

Vinay Khatri
Last updated on September 8, 2022

    Python List is one of the widely used Python data containers. A list can store multiple data objects. Also, it can store any type of Python data object, including itself. A list containing a list is known as a multi-dimensional list, and it could be 2D, 3D, or multi-dimensional.

    Often in Python interviews, interviewers ask to flatten a Python list that is actually a list of lists, and you need to convert it into a linear or 1-D list.

    For Example

    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, you will learn how to flatten a Python 2-D and multi-dimensional list into a 1-D list, or you can say, flatten a list of lists.

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

    A 2D list is a list of 1D lists. Converting a 2D list to a 1D list is easy, and we can use the following two techniques to achieve the same:

    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 Python for loop . In this approach, we use for loop and iterate 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 the 2D list and extend it to the one_d list.
    3. Use 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 the extend method itself is O(N). Thus, the overall time complexity of the above program is O(N^2).
    • Space Complexity: As we are using an extra empty list, the space complexity of the above program becomes O(N) . Here N is the total number of elements present in the List.

    In the above program instead of using the extend method, we can use 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-in itertools module that deals with different Python iterators. The itertools module supports a chain() function that accepts a series of iterable and returns a single iterable. We can use the itertools chain() function to convert a 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 Multi-level or Multi-D Python List to a 1D List?

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

    During an interview, if the interviewer asks you to convert a multi-level list to a 1D list, you cannot use the for loop or itertools chain() function because you are not certain about the depth of the nested list. In that case, you 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.

    Program to Convert a Multi-level or Multi-D Python List to a 1D List

    # 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]

    Behind the code: In the above program, we first initialized an empty array one_d that is supposed to store all the elements like a 1D list. In the flat_multi() function, we created a for loop that iterates over every element of the multi list and recursively calls the flat_multi() function if the element is a list.

    Otherwise, it appends the single element to the one_d list. 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 list of lists in Python. 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.

    If an interviewer asks you to flatten a list during an interview, it would be best to use the recursion method to do the same.

    People are also reading:

    Leave a Comment on this Post

    0 Comments