MediumPython

Flatten a nested list

Flatten [1, [2, [3, 4]], 5] into [1, 2, 3, 4, 5] for any depth.

Nested lists turn up whenever data comes from JSON: an API response, a config file, scraped data. Flattening them is a good test of whether you're comfortable with recursion.

Cases to check:

[1, [2, [3, 4]], 5] → [1, 2, 3, 4, 5]
[] → []
[[[]]] → []
[1, 'ab', [2]] → [1, 'ab', 2] (a string is not a list, so don't break it into letters)

That last one catches people who check "is it iterable?" instead of "is it a list?".

Starter code

def flatten(items):
    pass

💡 Hint 1

Recursion or a stack

✅ Show solution

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

How it works

For each item: if it's a list, flatten it (that's the recursion) and add all the results; otherwise add the item itself. The recursion stops naturally when it reaches items that aren't lists.

One style note: using a conditional expression just for its side effects (out.extend(...) if ... else out.append(...)) is compact, but a lot of reviewers prefer a normal if/else. In a real codebase I'd write it out.

Without recursion

Python has a recursion limit of about 1,000 levels. Very deep nesting would crash the version above. A stack avoids that:

def flatten(items):
    out, stack = [], [iter(items)]
    while stack:
        for x in stack[-1]:
            if isinstance(x, list):
                stack.append(iter(x))
                break
            out.append(x)
        else:
            stack.pop()
    return out

It keeps a stack of "where I was" in each list, and goes back up when a list runs out.

As a generator

If the data is big, yield items instead of building a list:

def flatten(items):
    for x in items:
        if isinstance(x, list):
            yield from flatten(x)
        else:
            yield x

Call list(flatten(data)) when you need the whole thing.

Complexity: O(n) time, where n is the total number of items at every level.

Tip: run your code in a local Python environment, Jupyter or Google Colab.