Katkat
Back

Flatten a Nested Integer List

AirbnbSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Flatten an arbitrarily deep mixture of integers and lists while preserving left-to-right order. The challenge emphasizes an iterative stack solution that handles empty lists, very deep nesting, and up to 200,000 nodes without mutating the input.

Flatten a Nested Integer List

A nested list contains either integers or other nested lists, to arbitrary depth. Return all integers in left-to-right order as one flat list.

Function Signature

def flatten_nested(values: list) -> list[int]:

Examples

Input: [1, [2, [3, 4], []], 5]
Output: [1, 2, 3, 4, 5]

Input: [[[]], -1, [0]]
Output: [-1, 0]

Constraints

  • The structure contains only Python integers and Python lists.
  • The total number of list nodes and integers is at most 200_000.
  • Nesting may be deep enough that recursion depth should be considered.
  • Do not mutate the input.

Clarifications

  • Empty lists contribute no output values.
  • Integer order is the depth-first, left-to-right order in the original structure.

Hints

  • Identify the work that must be preserved when descending into a nested list.
  • An explicit stack can avoid reliance on the language recursion limit.