3

To Convert a 2D array into 1D array in python , i found this method on leetcode. But can't find How its working logically step by step ? Please explain. Also someone said on leetcode that : "This could be quadratic runtime complexity when array size gets really large"

Is this true? if yes, How?

a = [[4,2,5],[1,8,2],[7,5,6]]
flat  = sum(a,[])
flat

output : [4, 2, 5, 1, 8, 2, 7, 5, 6]

Saurav Singh
  • 47
  • 2

2 Answers2

2

How sum works?

In Python, lists can be concatenated with operator +:

>>> [1] + [2, 3]
[1, 2, 3]

The sum function in Python is similar to:

>>> def my_sum(iterable, start=0):
...     for v in iterable:
...         start = start + v
...     return start
...

So for sum(a, []), you can understand the following operations:

>>> [] + [4, 2, 5] + [1, 8, 2] + [7, 5, 6]
[4, 2, 5, 1, 8, 2, 7, 5, 6]

But this will not be a good practice, because each concatenation will produce a new list, rather than concatenation in place on one of the lists:

>>> a = [1]
>>> b = [2, 3]
>>> c = a + b
>>> a, b, c
([1], [2, 3], [1, 2, 3])

This means that each concatenation requires O(n + m) time (n and m are the lengths of the two lists respectively), rather than O(m). For m lists with length n, the first time a list of length n will be concatenated with another list of length n, and the next time a list of length 2n will be concatenated with a list of length n... at the end, the total time spent will be:

(n + n) + (2n + n) + ... + (mn + n) = (m^2 + 3m) * n / 2 = O(m^2 * n)

Better practice

The simple method is to use in place concatenate each time:

def concatenate(lists):
    result = []
    for lst in lists:
        result += lst
    return result

A more concise way is to use functools.reduce and operator.iconcat:

>>> from functools import reduce
>>> from operator import iconcat
>>> reduce(iconcat, a, [])
[4, 2, 5, 1, 8, 2, 7, 5, 6]

You can also use itertools.chain.from_iterable to chain these lists, and then use the list to construct:

>>> from itertools import chain
>>> list(chain.from_iterable(a))
[4, 2, 5, 1, 8, 2, 7, 5, 6]

Or use nested list comprehension:

>>> [val for lst in a for val in lst]
[4, 2, 5, 1, 8, 2, 7, 5, 6]

For performance comparison, please refer to: How do I make a flat list out of a list of lists?

Mechanic Pig
  • 6,756
  • 3
  • 10
  • 31
-1

Here sum() works as follows: By default, sum() takes one required parameter which is a sequence of integers, as for the second optional parameter, it is defaulted to 0 to indicate that the sequence is of type int. However, in the above case, it passes list of lists to sum() with the optional start parameter set to [] to indicate the sequence type is list which concatenates them.

However, there are better solutions to this problem. One of which is to use a for loop.

For further information, please check the documentation.

Abdullrahman Elsayed
  • 1
  • 3