Flatten a Nested List
Problem
You are given a list whose items are either integers or further lists, nested to any depth. Return a single flat list holding every integer in the order they appear when reading the structure left to right. Empty lists contribute nothing.
Examples
Input: items = [1, [2, [3, 4]], 5]
Output: [1, 2, 3, 4, 5]
Why: depth does not change the reading orderInput: items = [[], [[]], [1]]
Output: [1]
Why: empty lists at any depth disappearInput: items = []
Output: []
Why: edge case, nothing to read at allHints
0 / 3
Look at a single item rather than the whole structure. There are only two kinds of item, and one of them is easy.
A nested list is the same problem in miniature. Whatever function solves the outer list already solves the inner one.
Walk the items once. Append an integer straight to the result; for a list, call the function on it and extend the result with what comes back. The empty list is the natural base case.
Solution
Every item is either a value to keep or a smaller copy of the same problem, which is exactly the shape recursion is for. Walking the items in order preserves the reading order, and extending with the sub-result keeps the nesting invisible in the output. The empty list needs no special case: the loop simply never runs. Every integer and every list node is visited once, so time is O(n) in the total number of nodes, and the stack goes as deep as the nesting does.
def flatten(items):
flat = []
for item in items:
if isinstance(item, list):
flat.extend(flatten(item)) # a nested list is a smaller problem
else:
flat.append(item)
return flat
print(flatten([1, [2, [3, 4]], 5])) # -> [1, 2, 3, 4, 5]
print(flatten([[], [[]], [1]])) # -> [1]
print(flatten([])) # -> []Stuck on the idea rather than the code? Recursion Basics covers it.