🏷️ Category: Lists / Recursion | 🎯 Difficulty: Medium | 🔥 Frequency: ★★★★☆
📋 Problem Statement
Given a nested list of integers (any depth), return a flat list with all integers. This process is essential to Flatten a Nested List.
📥 Input → [1, [2, [3, 4]], [5, 6]]
📤 Output → [1, 2, 3, 4, 5, 6]
📥 Input → [[1, 2], [3, [4, [5]]]]
📤 Output → [1, 2, 3, 4, 5]
📥 Input → [1, 2, 3]
📤 Output → [1, 2, 3]
🧠 What the Interviewer is Testing
| Concept | Why It Matters |
|---|---|
| Recursion | Handle arbitrary depth |
| isinstance() check | Type-aware iteration |
| extend vs append | List building |
💡 Approach
For each item in the list:
→ If item is a list → recurse into it (flatten it too)
→ If item is a value → append directly to result
✅ Optimal Solution — Recursive
def flatten(nested: list) -> list:
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse
else:
result.append(item) # base value
return result
# ── Test Cases ─────────────────────────────────
print(flatten([1, [2, [3, 4]], [5, 6]])) # ✅ [1, 2, 3, 4, 5, 6]
print(flatten([[1, 2], [3, [4, [5]]]])) # ✅ [1, 2, 3, 4, 5]
print(flatten([1, 2, 3])) # ✅ [1, 2, 3]
print(flatten([])) # ✅ []
🔄 Iterative Alternative (using a stack)
def flatten_iterative(nested: list) -> list:
stack = nested[::-1] # reverse so we pop from front
result = []
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(item[::-1])
else:
result.append(item)
return result
📊 Complexity Analysis
┌─────────────┬────────────────────────────────────────────┐
│ Time O(n) │ n = total number of elements at all levels │
│ Space O(d) │ d = depth of nesting (recursion stack) │
└─────────────┴────────────────────────────────────────────┘
🎤 How to Explain in the Interview
“I’ll use recursion. For each item, if it’s a list I recursively flatten it and extend my result. If it’s a value I append directly. This handles arbitrary depth nesting in O(n) time where n is the total number of elements.”
“I’ll use recursion. For each item, if it’s a list I recursively flatten it and extend my result. If it’s a value I append directly. This handles arbitrary depth nesting in O(n) time where n is the total number of elements.”
🔁 Common Follow-up Questions
Q1 → Flatten only one level deep?
import itertools
def flatten_one_level(nested):
return list(itertools.chain.from_iterable(nested))
Q2 → Using a generator?
def flatten_gen(nested):
for item in nested:
if isinstance(item, list):
yield from flatten_gen(item)
else:
yield item
# Memory efficient for large structures
📁 Set 1 of 4 — Python Interview Prep Series — devprepguide.com