Write a function to flatten a list of lists into a single list.
For one level of nesting, use a nested comprehension: [x for row in rows for x in row]. For arbitrary depth, use recursion and check isinstance(item, list). The flat version is O(n) in the number of elements.
Explain it simply
In a nested comprehension the loops read in the same order as in normal nested for statements: outer loop first, inner loop second.
Line by line
def flatten_once(rows):
return [x for row in rows for x in row]
def flatten_deep(items):
result = []
for item in items:
if isinstance(item, list):
result.extend(flatten_deep(item))
else:
result.append(item)
return result
print(flatten_once([[1, 2], [3], [4, 5]])) # Output: [1, 2, 3, 4, 5]
print(flatten_deep([1, [2, [3, [4]], 5]])) # Output: [1, 2, 3, 4, 5]
print(flatten_once([])) # Output: []flatten_deep handles any depth: lists are opened up recursively, other values are collected. Strings are deliberately not unpacked, since only list triggers recursion.
Complexity
Time O(n) where n is the total number of elements. Space O(n) for the result, plus recursion depth for the deep version.
What to say in the interview
"If the nesting is exactly one level, I use a nested comprehension. If depth is unknown, I recurse and extend with the flattened sublist. I'd mention that deep recursion can hit the recursion limit, and ask whether tuples or other iterables count as nested."