Python problem 15 of 30

Flatten a nested list

Python
Medium

Write flatten(items) that takes a list which may contain other lists, nested to any depth, and returns one flat list of all the non-list values in order.

flatten([1, [2, [3, 4]], [], 5])
# [1, 2, 3, 4, 5]

Show hint

A list of lists is the same problem, just smaller. Use recursion, and check each item with isinstance(x, list).

Show solution

def flatten(items):
    out = []
    for x in items:
        if isinstance(x, list):
            out.extend(flatten(x))
        else:
            out.append(x)
    return out

Each item is either a value (keep it) or a list (flatten it and add the results). Every value is visited once, so it runs in O(n) time for n total values. Very deep nesting can hit Python's recursion limit, around 1000 levels.

Want a problem like this every day? See today's problem and keep a streak going.