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

By Long Luo

This article is the solution 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:

    • NestedIterator\texttt{NestedIterator}: O(n)O(n).
    • next()\texttt{next()}: O(1)O(1)
    • hasNext()\texttt{hasNext()}: O(1)O(1)
  • Space Complexity: O(n)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:

    • NestedIterator\texttt{NestedIterator}: O(1)O(1).
    • next()\texttt{next()}: O(1)O(1)
    • hasNext()\texttt{hasNext()}: O(1)O(1)
  • Space Complexity: O(n)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. 😉😃💗