Optimize flattening for in-place

Question

Given a nested list of integers, implement a function that flattens the list in-place, meaning you should modify the input list directly without using additional data structures for storage. The function should return the length of the flattened list, and the elements should be arranged in a single-level list format.

Codemia · Accepted Answer

This problem involves flattening a nested list of integers in-place without using additional data structures. The main challenge is to handle varying levels of nesting and ensure that we maintain the order of elements. The best-fit pattern for this problem is Depth-First Search (DFS), as it allows us to traverse the nested structures recursively, processing each integer as we encounter it. Since we need to modify the input list directly, we will use two pointers: one to track the current position in the flattened list and another to traverse through the nested list.

We will use a recursive approach to flatten the list. The algorithm works as follows:
1. Initialize a pointer (let's call it `write_index`) at the start of the list.
2. For each element in the current list:
   - If the element is an integer, place it at `write_index` and increment `write_index`.
   - If the element is a list, recursively flatten that list and add its elements in the same way.
3. Continue until all elements have been processed. 
4. Finally, truncate the list to the size of `write_index` to reflect the new flattened structure.

**Example:** Given `nested_list = [1, [2, [3, 4]], 5]`, the steps would be:
- Process `1` → `write_index` moves to `1`, list becomes `[1, ...]`
- Process `[2, [3, 4]]` → recursively process `2` → `write_index` moves to `2`, list becomes `[1, 2, ...]`
- Process `[3, 4]` → process `3` → `write_index` moves to `3`, list becomes `[1, 2, 3, ...]`
- Process `4` → `write_index` moves to `4`, list becomes `[1, 2, 3, 4]`
- Finally, add `5` → `write_index` moves to `5`, list becomes `[1, 2, 3, 4, 5]`.

Here's the Python code implementing the above approach:
```python
def flatten(nested_list):
    write_index = 0
    def dfs(sublist):
        nonlocal write_index
        for item in sublist:
            if isinstance(item, int):
                nested_list[write_index] = item
                write_index += 1
            elif isinstance(item, list):
                dfs(item)
    dfs(nested_list)
    return write_index
```

The time complexity of this solution is O(n), where n is the total number of integers in the nested list. This is because every integer is processed exactly once. The space complexity is O(d) for the recursion stack, where d is the maximum depth of the nested list. Since we are not using any additional data structures, the approach adheres to the in-place requirement.

1. **Empty List**: If the input list is empty (`[]`), the function should return `0` as there are no elements to flatten.
2. **Single Integer**: If the list contains a single integer (`[42]`), the function should return `1` and the list should remain unchanged.
3. **Deep Nesting**: If the list is deeply nested (e.g., `[[[[1]]]]`), the function should correctly handle this without exceeding recursion limits.
4. **Mixed Types**: Input like `[1, 'two', [3]]` should be considered invalid, as per typical constraints, but if allowed, the function should ideally raise an error or skip non-integer elements.

Optimize flattening for in-place

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Airbnb Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string