Flatten Nested List Iterator

Flatten Nested List Iterator

1. What is this problem about?

The Flatten Nested List Iterator interview question asks you to build a specialized iterator that can traverse a deeply nested data structure. You are given a list of "NestedIntegers," each of which is either a single integer or another list of NestedIntegers. Your task is to implement next() and hasNext() methods so that a user can iterate through all integers in the structure as if they were in a simple 1D array.

2. Why is this asked in interviews?

This is a classic Design interview pattern question used by companies like LinkedIn, Netflix, and Apple. It evaluates your ability to handle recursion and state management simultaneously. Interviewers want to see if you can implement a "lazy" iterator—one that only does the work necessary to find the next integer—rather than simply flattening the entire list into memory upfront, which is inefficient for massive datasets.

3. Algorithmic pattern used

The most robust approach uses a Stack-based Iterator pattern.

1. Stack of Iterators: Instead of flattening the list, you maintain a stack that holds iterators of the nested lists.
2. Depth-First Search (DFS): When hasNext() is called, you look at the top iterator. If it points to another list, you push a new iterator for that sub-list onto the stack.
3. Lazy Evaluation: You continue this process until the top iterator points to a single integer or the stack is empty. This ensures that you only process as much of the structure as needed for each next() call.

4. Example explanation

Consider the input: [[1, 1], 2, [3, 4]].

1. Start: The stack contains an iterator for the main list.
2. First hasNext(): It sees the first element is a list [1, 1]. It pushes an iterator for [1, 1] onto the stack.
3. Next(): It returns the 1 from the top iterator.
4. Subsequent calls: Once the [1, 1] iterator is exhausted, it is popped, and the stack returns to the main list iterator, which now points to 2.

5. Common mistakes candidates make

• Pre-flattening: The biggest mistake is flattening the entire structure in the constructor. While this works for small inputs, it violates the "iterator" principle of memory efficiency and can fail on extremely large or infinite data streams.
• Empty Lists: Failing to handle empty nested lists like [1, [], [2]]. A naive hasNext() might return true for the empty list but then fail to find an integer.
• State Corruption: Modifying the input structure or losing track of where the iterator is currently pointing during complex nesting transitions.

6. Interview preparation tip

When designing iterators for recursive structures, always think about the Stack or Recursion as your primary tool. Practice the "lazy" approach, as it demonstrates that you understand the trade-offs between time and space complexity in system design. Mastering this Iterator interview pattern is key to solving many tree and graph traversal problems.