# Evolve from intuition to optimal, a review of top solutions

1. O(n) space, Flatten the list in constructor. The nested list can be visualized as a tree and the iterator order is dfs.
``````class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
dfs(nestedList);
}
void dfs(vector<NestedInteger> &nestedList) {
for(int i=nestedList.size()-1;i>=0;i--)
if(nestedList[i].isInteger()) stk.push(nestedList[i].getInteger());
else dfs(nestedList[i].getList());
}
int next() {
int nxt = stk.top();
stk.pop();
return nxt;
}
bool hasNext() {
return !stk.empty();
}
private:
stack<int> stk;
};
``````
1. O(n) space, Flatten the list as you go. #1 is not an iterator because an iterator should never copy the data structure. Besides, it is a waste of time to flatten and store the whole list if we may only visit a few elements. So we can store the first level in the stack and flatten it as we go. If the list is flat, then there is no saving over #1.
``````class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for(int i=nestedList.size()-1;i>=0;i--) stk.push(&nestedList[i]);
}
int next() {
int nxt = stk.top()->getInteger();
stk.pop();
return nxt;
}
bool hasNext() {
while(!stk.empty()) {
NestedInteger *p = stk.top();
if(p->isInteger()) return 1;
vector<NestedInteger> &vec = p->getList();
stk.pop();
for(int i=vec.size()-1;i>=0;i--) stk.push(&vec[i]);
}
return 0;
}
private:
stack<NestedInteger*> stk;
};
``````
1. O(h) space, Real iterator. #2 stores pointers to each element in the current list. This still can be large. The following solution only stores 2 iterators of the current list. The great idea is from @StefanPochmann. h is the depth of the list.
``````class NestedIterator {
public:
typedef vector<NestedInteger>::iterator iter;
NestedIterator(vector<NestedInteger> &nestedList) {
begins.push(nestedList.begin());
ends.push(nestedList.end());
}
int next() {
return begins.top()++->getInteger();
}
bool hasNext() {
while(!begins.empty()) {
iter it = begins.top();
if(it == ends.top()) {
begins.pop();
ends.pop();
if(!begins.empty()) begins.top()++;
} else if (it->isInteger()) return 1;
else {
vector<NestedInteger>& lst = it->getList();
begins.push(lst.begin());
ends.push(lst.end());
}
}
return 0;
}
private:
stack<iter> begins, ends;
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.