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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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. 😉😃💗