Flatten Nested List¶

Problem¶

Given a nested list of integers (can be arbitrarily deep), flatten it into a single list of integers.

Approach¶

Recursive: if element is a list, recurse into it; otherwise yield the integer. Also provide an iterative version using an explicit stack (process in reverse to maintain order).

When to Use¶

Processing recursive/nested data structures — JSON, XML, file trees, AST traversal. ASI relevance: nested geospatial data, hierarchical flight plans.

Complexity¶


Time	`O(n) — where n = total elements across all nesting levels`
Space	`O(d) recursive / O(n) iterative — d = max depth`

Implementation¶

SolutionTestsChallenge

flatten_nested_list ¶

Flatten Nested List — recursively flatten arbitrarily deep lists.

Problem

Given a nested list of integers (can be arbitrarily deep), flatten it into a single list of integers.

Approach

Recursive: if element is a list, recurse into it; otherwise yield the integer. Also provide an iterative version using an explicit stack (process in reverse to maintain order).

When to use

Processing recursive/nested data structures — JSON, XML, file trees, AST traversal. ASI relevance: nested geospatial data, hierarchical flight plans.

Complexity

Time: O(n) — where n = total elements across all nesting levels Space: O(d) recursive / O(n) iterative — d = max depth

flatten_iterative ¶

flatten_iterative(nested: NestedList) -> list[int]

Flatten nested list of integers iteratively using a stack.

flatten_iterative([1, [2, [3, 4], 5], 6]) [1, 2, 3, 4, 5, 6] flatten_iterative([]) []

Source code in src/algo/recursion/flatten_nested_list.py

def flatten_iterative(nested: NestedList) -> list[int]:
    """Flatten *nested* list of integers iteratively using a stack.

    >>> flatten_iterative([1, [2, [3, 4], 5], 6])
    [1, 2, 3, 4, 5, 6]
    >>> flatten_iterative([])
    []
    """
    result: list[int] = []
    stack: list[int | list[Any]] = list(reversed(nested))
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            for sub in reversed(item):
                stack.append(sub)
        else:
            result.append(item)
    return result

flatten_recursive ¶

flatten_recursive(nested: NestedList) -> list[int]

Flatten nested list of integers recursively.

flatten_recursive([1, [2, [3, 4], 5], 6]) [1, 2, 3, 4, 5, 6] flatten_recursive([]) []

Source code in src/algo/recursion/flatten_nested_list.py

def flatten_recursive(nested: NestedList) -> list[int]:
    """Flatten *nested* list of integers recursively.

    >>> flatten_recursive([1, [2, [3, 4], 5], 6])
    [1, 2, 3, 4, 5, 6]
    >>> flatten_recursive([])
    []
    """
    return list(_flatten_helper(nested))

tests/recursion/test_flatten_nested_list.py

"""Tests for the flatten nested list problem."""

from typing import Any

from hypothesis import given
from hypothesis import strategies as st

from algo.recursion.flatten_nested_list import flatten_iterative, flatten_recursive


class TestFlattenRecursive:
    def test_basic(self) -> None:
        assert flatten_recursive([1, [2, [3, 4], 5], 6]) == [1, 2, 3, 4, 5, 6]

    def test_empty(self) -> None:
        assert flatten_recursive([]) == []

    def test_already_flat(self) -> None:
        assert flatten_recursive([1, 2, 3]) == [1, 2, 3]

    def test_deeply_nested(self) -> None:
        assert flatten_recursive([[[[[1]]]]]) == [1]

    def test_mixed_nesting(self) -> None:
        assert flatten_recursive([1, [2], [[3]], [[[4]]]]) == [1, 2, 3, 4]

    def test_empty_sublists(self) -> None:
        assert flatten_recursive([1, [], [2, []], 3]) == [1, 2, 3]


class TestFlattenIterative:
    def test_basic(self) -> None:
        assert flatten_iterative([1, [2, [3, 4], 5], 6]) == [1, 2, 3, 4, 5, 6]

    def test_empty(self) -> None:
        assert flatten_iterative([]) == []

    def test_already_flat(self) -> None:
        assert flatten_iterative([1, 2, 3]) == [1, 2, 3]

    def test_deeply_nested(self) -> None:
        assert flatten_iterative([[[[[1]]]]]) == [1]

    def test_empty_sublists(self) -> None:
        assert flatten_iterative([1, [], [2, []], 3]) == [1, 2, 3]


class TestFlattenEquivalence:
    @given(
        data=st.lists(
            st.integers(min_value=-100, max_value=100),
            min_size=0,
            max_size=20,
        ),
    )
    def test_both_match_on_flat_input(self, data: list[int]) -> None:
        assert flatten_recursive(data) == flatten_iterative(data) == data

    def test_both_match_on_nested_input(self) -> None:
        nested: list[int | list[Any]] = [1, [2, 3], [4, [5, [6]]], 7, [[8]]]
        expected = [1, 2, 3, 4, 5, 6, 7, 8]
        assert flatten_recursive(nested) == expected
        assert flatten_iterative(nested) == expected

Implement it yourself

Run: just challenge recursion flatten_nested_list

Then implement the functions to make all tests pass. Use just study recursion for watch mode.

Reveal Solution

flatten_nested_list ¶

Flatten Nested List — recursively flatten arbitrarily deep lists.

Problem

Given a nested list of integers (can be arbitrarily deep), flatten it into a single list of integers.

Approach

Recursive: if element is a list, recurse into it; otherwise yield the integer. Also provide an iterative version using an explicit stack (process in reverse to maintain order).

When to use

Processing recursive/nested data structures — JSON, XML, file trees, AST traversal. ASI relevance: nested geospatial data, hierarchical flight plans.

Complexity

Time: O(n) — where n = total elements across all nesting levels Space: O(d) recursive / O(n) iterative — d = max depth

flatten_iterative ¶

flatten_iterative(nested: NestedList) -> list[int]

Flatten nested list of integers iteratively using a stack.

flatten_iterative([1, [2, [3, 4], 5], 6]) [1, 2, 3, 4, 5, 6] flatten_iterative([]) []

Source code in src/algo/recursion/flatten_nested_list.py

def flatten_iterative(nested: NestedList) -> list[int]:
    """Flatten *nested* list of integers iteratively using a stack.

    >>> flatten_iterative([1, [2, [3, 4], 5], 6])
    [1, 2, 3, 4, 5, 6]
    >>> flatten_iterative([])
    []
    """
    result: list[int] = []
    stack: list[int | list[Any]] = list(reversed(nested))
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            for sub in reversed(item):
                stack.append(sub)
        else:
            result.append(item)
    return result

flatten_recursive ¶

flatten_recursive(nested: NestedList) -> list[int]

Flatten nested list of integers recursively.

flatten_recursive([1, [2, [3, 4], 5], 6]) [1, 2, 3, 4, 5, 6] flatten_recursive([]) []

Source code in src/algo/recursion/flatten_nested_list.py

def flatten_recursive(nested: NestedList) -> list[int]:
    """Flatten *nested* list of integers recursively.

    >>> flatten_recursive([1, [2, [3, 4], 5], 6])
    [1, 2, 3, 4, 5, 6]
    >>> flatten_recursive([])
    []
    """
    return list(_flatten_helper(nested))