341. Flatten Nested List Iterator

  • 40.0%

https://leetcode.com/problems/flatten-nested-list-iterator/#/description

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

1
2
3
4
Example 1:
Given the list [[1,1],2,[1,1]],

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

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

Real iterator in Python, Java, C++

In my opinion an iterator shouldn’t copy the entire data (which some solutions have done) but just iterate over the original data structure.

I keep the current progress in a stack. My hasNext tries to find an integer. My next returns it and moves on. I call hasNext in next because hasNext is optional. Some user of the iterator might call only next and never hasNext, e.g., if they know how many integers are in the structure or if they want to handle the ending with exception handling.

Python

Using a stack of [list, index] pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class NestedIterator(object):

def __init__(self, nestedList):
self.stack = [[nestedList, 0]]

def next(self):
self.hasNext()
nestedList, i = self.stack[-1]
self.stack[-1][1] += 1
return nestedList[i].getInteger()

def hasNext(self):
s = self.stack
while s:
nestedList, i = s[-1]
if i == len(nestedList):
s.pop()
else:
x = nestedList[i]
if x.isInteger():
return True
s[-1][1] += 1
s.append([x.getList(), 0])
return False

Java

Using a stack of ListIterators.

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
public class NestedIterator implements Iterator<Integer> {

public NestedIterator(List<NestedInteger> nestedList) {
lists = new Stack<>();
lists.push(nestedList.listIterator());
}

public Integer next() {
hasNext();
return lists.peek().next().getInteger();
}

public boolean hasNext() {
while (!lists.empty()) {
if (!lists.peek().hasNext()) {
lists.pop();
} else {
NestedInteger x = lists.peek().next();
if (x.isInteger())
return lists.peek().previous() == x;
lists.push(x.getList().listIterator());
}
}
return false;
}

private Stack<ListIterator<NestedInteger>> lists;
}

C++

Using stacks of begin and end iterators.

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
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
begins.push(nestedList.begin());
ends.push(nestedList.end());
}

int next() {
hasNext();
return (begins.top()++)->getInteger();
}

bool hasNext() {
while (begins.size()) {
if (begins.top() == ends.top()) {
begins.pop();
ends.pop();
} else {
auto x = begins.top();
if (x->isInteger())
return true;
begins.top()++;
begins.push(x->getList().begin());
ends.push(x->getList().end());
}
}
return false;
}

private:
stack<vector<NestedInteger>::iterator> begins, ends;
};

https://discuss.leetcode.com/topic/41846/concise-c-without-storing-all-values-at-initialization

Concise C++ without storing all values at initialization

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
class NestedIterator {
private:
stack<NestedInteger> nodes;

public:
NestedIterator(vector<NestedInteger> &nestedList) {
int size = nestedList.size();
for(int i = size - 1; i >= 0; --i) {
nodes.push(nestedList[i]);
}
}

int next() {
int result = nodes.top().getInteger();
nodes.pop();
return result;
}

bool hasNext() {
while(!nodes.empty()) {
NestedInteger curr = nodes.top();
if(curr.isInteger()) {
return true;
}

nodes.pop();
vector<NestedInteger>& adjs = curr.getList();
int size = adjs.size();
for(int i = size - 1; i >= 0; --i) {
nodes.push(adjs[i]);
}
}

return false;
}
};

The same idea as a DFS, the only tricky part probably is you have to find a value node to claim there is next. And to do that, you have to look through all the nodes in the worst case in the entire graph. So you just keep going until you find a value node; if you can’t, there is no next.


https://discuss.leetcode.com/topic/45844/python-generators-solution

Python Generators solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NestedIterator(object):

def __init__(self, nestedList):
def gen(nestedList):
for x in nestedList:
if x.isInteger():
yield x.getInteger()
else:
for y in gen(x.getList()):
yield y
self.gen = gen(nestedList)

def next(self):
return self.value

def hasNext(self):
try:
self.value = next(self.gen)
return True
except StopIteration:
return False

This assumes that the iterator is just used as described in the problem. Usually, hasNext should be both optional and idempotent, but a next+hasNext iterator is very unpythonic anyway, so I decided to not do that here, as I feel it would distract from the generator.

And of course while this solution is (IMHO) somewhat cute, it passes each value through each level it’s nested in, so it’s not efficient.


32ms, , 44/44, April.24th, 2016

https://leetcode.com/discuss/98689/simple-cpp-solution

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
class NestedIterator {
public:
vector<int> a;
int index = 0;
NestedIterator(vector<NestedInteger> &nestedList) {
convert(nestedList, nestedList.size());
}

void convert(vector<NestedInteger> &nestedList, int size){
int i;
for(i = 0; i < size; i++){
if(nestedList[i].isInteger()) a.push_back(nestedList[i].getInteger());
else convert(nestedList[i].getList(), nestedList[i].getList().size());
}
}

int next() {
return a[index++];
}

bool hasNext() {
if(index < a.size())
return 1;
return 0;
}
};

124ms, , 44/44, April.24th, 2016

https://leetcode.com/discuss/98134/share-my-cpp-and-python-solution-with-recursion

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
class NestedIterator(object):

def __init__(self, nestedList):
self.my_list = []
self.index = 0
for i in nestedList:
if i.isInteger() == True:
self.my_list.append(i.getInteger())
else:
self.read_list(i.getList())
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
def read_list(self,l):
for i in l:
if i.isInteger() == True:
self.my_list.append(i.getInteger())
else:
self.read_list(i.getList())


def next(self):
"""
:rtype: int
"""
re = self.my_list[self.index]
self.index += 1
return re


def hasNext(self):
"""
:rtype: bool
"""
if self.index == len(self.my_list):
return False
return True
谢谢你,可爱的朋友。