Flatten Nested List

Problem

Configuration parsers and data pipeline schemas often receive inputs with variable-depth nesting - a list where each element is either a value or another (possibly nested) list. Flattening to a single level is a prerequisite for most downstream processing. Given a nested list of integers (to any depth), return a flat list containing all integers in their original left-to-right order.

Input: [1, [2, 3], [4, [5, 6]], 7]    → [1, 2, 3, 4, 5, 6, 7]
Input: [[1, [2]], [3, [4, [5]]]]       → [1, 2, 3, 4, 5]
Input: []                              → []
Input: [1, 2, 3]                       → [1, 2, 3]

Solution

Approach: Structural recursion that mirrors the nesting - recurse on lists, collect plain values.

The function walks the list left to right and asks one question per element: is it a list or a plain value? isinstance(element, list) makes the distinction. A plain value is the base case - it is appended directly to result with no further recursion. A sub-list is the recursive case - flatten(element) returns a fully flat list of everything inside it, and result.extend(...) merges those items into result in order. The choice of extend over append is the crux: extend unwraps the returned list and adds its items one by one, while append would insert the whole flat list as a single nested element, re-introducing the nesting you just removed. Because the recursion descends one call per nesting level, the code's depth automatically matches the data's depth, however irregular - no manual stack or depth tracking is needed.

Trace flatten([1, [2, 3], 7]): 1 is not a list, append -> [1]; [2, 3] is a list, recurse - that call appends 2 then 3 and returns [2, 3], which extend merges -> [1, 2, 3]; 7 is not a list, append -> [1, 2, 3, 7]. Left-to-right iteration preserves original order at every level.

Edge cases: An empty list returns [] because the loop body never runs. An already-flat list appends every element directly. Arbitrarily deep single-element nests like [[[3]]] simply recurse one extra level each, reaching the integer at the bottom.

Complexity: O(n) time, O(n + d) space - every one of n elements is visited once; the output holds n items and the call stack reaches d frames deep, where d is the maximum nesting depth (worst case d = n).