## Tuesday, April 5, 2016

### LeetCode 341 - Flatten Nested List Iterator

http://www.cnblogs.com/grandyang/p/5358793.html
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.
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]`.
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]`.
- What if the NestedInteger can be null
X. Using Stack
https://discuss.leetcode.com/topic/42042/simple-java-solution-using-a-stack-with-explanation

A question before this is the Nested List Weight Sum, and it requires recursion to solve. As it carries to this problem that we will need recursion to solve it. But since we need to access each NestedInteger at a time, we will use a stack to help.
In the constructor, we push all the nestedList into the stack from back to front, so when we pop the stack, it returns the very first element. Second, in the hasNext() function, we peek the first element in stack currently, and if it is an Integer, we will return true and pop the element. If it is a list, we will further flatten it. This is iterative version of flatting the nested list. Again, we need to iterate from the back to front of the list.
call hasNext() before next() internally to avoid exception

``````public class NestedIterator implements Iterator<Integer> {

private Stack<NestedInteger> stack;

public NestedIterator(List<NestedInteger> nestedList) {
stack = new Stack<>();
flattenList(nestedList);
}

@Override
public Integer next() {
return hasNext() ? stack.pop().getInteger() : null;
}

@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
if (stack.peek().isInteger()) return true;
flattenList(stack.pop().getList());
}
return false;
}

private void flattenList(List<NestedInteger> list) {
for (int i = list.size() - 1; i >= 0; i--) {
stack.push(list.get(i));
}
}
}``````
X. Better Using a stack of ListIterators.
https://discuss.leetcode.com/topic/44983/share-my-java-neat-solution-8ms
what I do is just to keep an additional field storing the next integer
If we call hasNext() multiple times before calling next() it will not give the right result since you are calling next on Iterator<NestedInteger> in hasNext() method which means that every time you call hasNext() it will remove the next Integer from the list.
``````public class NestedIterator implements Iterator<Integer> {
Stack<Iterator<NestedInteger>> stack;
Integer nextInteger;
public NestedIterator(List<NestedInteger> nestedList) {
stack = new Stack<Iterator<NestedInteger>>();
stack.push(nestedList.iterator());
nextInteger = null;
}
public Integer next() {
Integer next = null;
if(hasNext()) {
next = nextInteger;
nextInteger=null;
}
return next;
}
public boolean hasNext() {
if(nextInteger==null) {
while(!stack.isEmpty()) {
Iterator<NestedInteger> cIterator = stack.peek();
if(cIterator.hasNext()) {
NestedInteger c = cIterator.next();
if(c.isInteger()) {
nextInteger = c.getInteger();
return true;
} else {
stack.push(c.getList().iterator());
}
}
else stack.pop();
}
return false;
} else return true;
}
}``````
https://leetcode.com/discuss/95937/simple-iterative-dfs-using-stack
`hasNext` should be idempotent and optional (so it can be called several times before each `next` or not at all, and `next` should still work properly).
public class NestedIterator implements Iterator<Integer> { Stack<Iterator<NestedInteger>> stack = new Stack<>(); Integer current = null; public NestedIterator(List<NestedInteger> nestedList) { if (nestedList != null) { stack.push(nestedList.iterator()); } } @Override public Integer next() { hasNext(); Integer value = current; current = null; return value; } @Override public boolean hasNext() { while (current == null && !stack.isEmpty()) { Iterator<NestedInteger> node = stack.peek(); if (!node.hasNext()) { stack.pop(); continue; } NestedInteger value = node.next(); if (value.isInteger()) { current = value.getInteger(); return true; } else { stack.push(value.getList().iterator()); } } return false; } }
https://discuss.leetcode.com/topic/41870/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.
``````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; //previous to cancel side effects of next. ==x, weird

lists.push(x.getList().listIterator());
}
}
return false;
}

private Stack<ListIterator<NestedInteger>> lists;
}``````
http://www.cnblogs.com/grandyang/p/5358793.html
```class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i = nestedList.size() - 1; i >= 0; --i) {
s.push(nestedList[i]);
}
}

int next() {
NestedInteger t = s.top(); s.pop();
return t.getInteger();
}

bool hasNext() {
while (!s.empty()) {
NestedInteger t = s.top();
if (t.isInteger()) return true;
s.pop();
for (int i = t.getList().size() - 1; i >= 0; --i) {
s.push(t.getList()[i]);
}
}
return false;
}

private:
stack<NestedInteger> s;
};```
https://leetcode.com/discuss/95846/easy-to-understand-java-solution
private List<Integer> elements = new LinkedList<>(); public NestedIterator(List<NestedInteger> nestedList) { if ( nestedList == null || nestedList.size() == 0) { return; } flatten(nestedList, elements); } @Override public Integer next() { int ret = -1; if (hasNext()) { ret = elements.remove(0); } return ret; } @Override public boolean hasNext() { return elements.size() > 0; } private void flatten(List<NestedInteger> nestedList, List<Integer> elements) { for (NestedInteger e: nestedList) { if (e.isInteger()) { elements.add(e.getInteger()); } else { flatten(e.getList(), elements); } } }
http://www.cnblogs.com/grandyang/p/5358793.html

https://leetcode.com/discuss/95849/java-dfs-solution
don't maintain the index explicitly,  use queue.remove, queue.isEmpty.
public class NestedIterator implements Iterator<Integer> { List<Integer> result; int index; public NestedIterator(List<NestedInteger> nestedList) { result = new ArrayList<Integer>(); index = 0; dfs(nestedList, result); } @Override public Integer next() { return result.get(index++); // use queue.remove } @Override public boolean hasNext() { return index != result.size(); } private void dfs(List<NestedInteger> list, List<Integer> result) { for(NestedInteger tmp : list) { if(tmp.isInteger()) result.add(tmp.getInteger()); else dfs(tmp.getList(), result); } }
http://www.jiuzhang.com/solutions/flatten-nested-iterate/

X. Just a different way but inefficent
https://discuss.leetcode.com/topic/42772/flatten-the-list-and-iterate-with-plain-next-and-hasnext-java
First flatten the list to a list of Integer by using DFS, then just call the plain `next()` and `hasNext()`
``````private List<Integer> flattenedList;
private Iterator<Integer> it;

public NestedIterator(List<NestedInteger> nestedList) {
flatten(nestedList);
it = flattenedList.iterator();
}

private void flatten(List<NestedInteger> nestedList) {
for (NestedInteger i : nestedList) {
if (i.isInteger()) {
} else {
flatten(i.getList());
}
}
}

@Override
public Integer next() {
return it.next();
}

@Override
public boolean hasNext() {
return it.hasNext();
}``````
https://discuss.leetcode.com/topic/80763/evolve-from-intuition-to-optimal-a-review-of-top-solutions