Flatten a Nested Integer List
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# 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
```python
def flatten_nested(values: list) -> list[int]:
```
### Examples
```text
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.
Quick Answer: 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 arbitrarily nested Python lists of integers into one left-to-right integer list without mutating the input.
Constraints
- The structure contains only lists and integers
- At most 200000 list nodes and integers
- Nesting may exceed recursion depth
Examples
Input: []
Expected Output: []
Explanation: An empty list contributes no integers.
Input: [1, [2, [3, 4], []], 5]
Expected Output: [1, 2, 3, 4, 5]
Explanation: Nested values retain depth-first left-to-right order.
Hints
- An explicit stack can store work that recursion would defer.
- Push a child list in reverse so its leftmost item is processed first.