How Not to Flatten a List of Lists in Python

You will find lots of solutions on the Web to flatten a list of lists in Python. Most of them take linear time, which is efficient because each element is copied once. But some solutions take more than linear time. In this article, I will explain why one of the simplest solution sum(lst, []) is actually one of the worst solution. The inefficiency comes from how the + operator (concatenation) is defined on a list: it creates a new list and copies each element into it.