[LeetCode][341. Flatten Nested List Iterator] 2 Approaches: DFS and Iteration(Using Stack)

By Long Luo

This article is the solution 2 Approaches: DFS and Iteration(Using Stack) of Problem 341. Flatten Nested List Iterator.

Here are 2 approaches to solve this problem in Java, DFS and Iteration approach.

DFS

We can store all the integers in an array, just traversing the array.

public class NestedIterator implements Iterator<Integer> {
    List<Integer> numList;
    int idx;

    public NestedIterator(List<NestedInteger> nestedList) {
        numList = new ArrayList<>();
        idx = 0;
        dfs(nestedList);
    }

    private void dfs(List<NestedInteger> nestedList) {
        if (nestedList == null) {
            return;
        }

        for (int i = idx; i < nestedList.size(); i++) {
            NestedInteger nested = nestedList.get(i);
            if (nested.isInteger()) {
                numList.add(nested.getInteger());
            } else {
                dfs(nested.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return numList.get(idx++);
    }

    @Override
    public boolean hasNext() {
        if (idx < numList.size()) {
            return true;
        }

        return false;
    }
}

Analysis

• Time Complexity:

  • $\texttt{NestedIterator}$: $O(n)$.
  • $\texttt{next()}$: $O(1)$
  • $\texttt{hasNext()}$: $O(1)$

• Space Complexity: $O(n)$.

Iteration (Using Stack)

We can use a Stack to maintain all nodes on the path from the root node to the current node.

The stack stores the iterators, which is a pointer to the element.

public class NestedIterator implements Iterator<Integer> {
    Deque<Iterator<NestedInteger>> stk;

    public NestedIterator(List<NestedInteger> nestedList) {
        stk = new ArrayDeque<>();
        stk.push(nestedList.iterator());
    }

    @Override
    public Integer next() {
        return stk.peek().next().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stk.isEmpty()) {
            Iterator<NestedInteger> iterator = stk.peek();
            if (!iterator.hasNext()) {
                stk.pop();
                continue;
            }

            NestedInteger nested = iterator.next();
            if (nested.isInteger()) {
                List<NestedInteger> list = new ArrayList<>();
                list.add(nested);
                stk.push(list.iterator());
                return true;
            }

            stk.push(nested.getList().iterator());
        }

        return false;
    }
}

Analysis

• Time Complexity:

  • $\texttt{NestedIterator}$: $O(1)$.
  • $\texttt{next()}$: $O(1)$
  • $\texttt{hasNext()}$: $O(1)$

• Space Complexity: $O(n)$.

The Iteration approach is better.

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗