Flatten Nested List Iterator

Problem Statement

In this problem, you are given a nested structure, where each element can either be a single integer or another nested list of integers. The challenge is to design and implement a NestedIterator class that effectively flattens this list. This iterator should allow for iterating through all integers in the nested list in a flattened manner.

The NestedIterator class will be constructed with the following methods:

• NestedIterator(List<NestedInteger> nestedList): This method initializes the iterator using the provided nested list.

• int next(): This function is used to return the next integer from the nested list.

• boolean hasNext(): This function checks if there are any more integers available in the nested list to access.

This nested list structure is recursively defined; thus, the elements can contain integers directly or other lists potentially containing more lists, and so on. The iterator will be used with a conventional approach to test if it functions correctly, by continually calling next() until hasNext() returns false, and appending each result to a resultant list. If this list matches the correctly flattened version of the input nested list, the implementation is considered correct.

Examples

Example 1

Input:

nestedList = [[1,1],2,[1,1]]

Output:

[1,1,2,1,1]

Explanation:

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2

Input:

nestedList = [1,[4,[6]]]

Output:

[1,4,6]

Explanation:

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-106, 106].

Approach and Intuition

The key to solving this problem lies in effectively managing the nested lists' traversal while ensuring that we can always quickly determine if more integers are left to iterate over. Here’s how we can approach this:

1. Initialization:

   • When NestedIterator is instantiated, initialize a stack or another suitable data structure to keep track of the nesting.
   • Convert the outer list into an iterable structure (e.g., stack or queue), starting with the outermost list and remembering the position within each inner list as you dive deeper into the structure.

2. hasNext() method:

   • This method checks if there are elements left to process.
   • Loop through the current top of the stack: if it’s an integer, return true; if it's a list, dive deeper.
   • Continue exploring deeper into any nested lists encountered along the way, adding them to the stack until you either find an integer or exhaust the possibilities.

3. next() method:

   • This should return the next available integer.
   • Ensure, usually by a preliminary call to hasNext(), that there indeed exists an integer to provide.
   • Pop integers off the stack for delivery until you need to dive back into nested lists to find more.

Example Walkthrough (with stack intuition):

• Consider nestedList = [[1,1],2,[1,1]]
  • Initialize by putting the entire nestedList onto the stack.
  • Start with the outer list. As you dive in, keep track of each element and subsection:
    • The section [[1,1]] is found; it's a list, so traverse and return 1, then again for the next 1.
    • Encounter 2, a standalone integer, return it.
    • Dive into the next section [1,1] and return 1 and 1 in subsequent calls.
  • Use hasNext() continually to dive as necessary and to backtrack when a subsection exhausts, always pushing and popping from the stack.

By using a stack, we efficiently backtrack out of nested substructures and manage our place within each level's structure. This design ensures we respect the order of elements and only dive as deep as necessary on each next() invocation, making this design both space and time efficient where it matters.

Solutions

import java.util.NoSuchElementException;

public class FlattenedListIterator implements Iterator<Integer> {

    private Deque<List<NestedInteger>> stackOfLists = new ArrayDeque<>();
    private Deque<Integer> stackOfIndices = new ArrayDeque<>();
    
    public FlattenedListIterator(List<NestedInteger> nestedList) {
        stackOfLists.addFirst(nestedList);
        stackOfIndices.addFirst(0);
    }
    
    @Override
    public Integer next() {
        if (!hasNext()) throw new NoSuchElementException();
        int index = stackOfIndices.removeFirst();
        stackOfIndices.addFirst(index + 1);
        return stackOfLists.peekFirst().get(index).getInteger();
    }

    @Override
    public boolean hasNext() {
        prepareNextInteger();
        return !stackOfIndices.isEmpty();
    }

    private void prepareNextInteger() {
        while (!stackOfIndices.isEmpty()) {
            if (stackOfIndices.peekFirst() >= stackOfLists.peekFirst().size()) {
                stackOfIndices.removeFirst();
                stackOfLists.removeFirst();
                continue;
            }

            if (stackOfLists.peekFirst().get(stackOfIndices.peekFirst()).isInteger()) {
                break;
            }

            stackOfLists.addFirst(stackOfLists.peekFirst().get(stackOfIndices.peekFirst()).getList());
            stackOfIndices.addFirst(stackOfIndices.removeFirst() + 1);
            stackOfIndices.addFirst(0);
        }
    }
}

function getLastElement(arr) {
    return arr[arr.length - 1];
}

class FlattenNestedListIterator {
    constructor(nestedList) {
        this._internalStack = [[nestedList, 0]];
    }

    _flattenNestedListToInteger() {
        while (this._internalStack.length > 0) {
            const [list, idx] = getLastElement(this._internalStack);
            
            // If the current list is entirely visited, remove it.
            if (list.length === idx) {
                this._internalStack.pop();
                continue;
            }
            
            // If the current element is an integer, no more action is required.
            if (list[idx].isInteger()) {
                break;
            }
            
            // If it's a list, then further process it.
            const newNestedList = list[idx].getList();
            getLastElement(this._internalStack)[1] += 1; // Move index ahead in the current list
            this._internalStack.push([newNestedList, 0]); // Push the new list onto the stack
        }
    }

    next() {
        this._flattenNestedListToInteger();
        const [currentList, idx] = getLastElement(this._internalStack);
        getLastElement(this._internalStack)[1] += 1;
        return currentList[idx].getInteger();
    }

    hasNext() {
        this._flattenNestedListToInteger();
        return this._internalStack.length > 0;
    }
}