## DEV Community is a community of 848,701 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Flatten Nested List Iterator

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the `NestedIterator` class:

• `NestedIterator(List<NestedInteger> nestedList)` Initializes the iterator with the nested list `nestedList`.
• `int next()` Returns the next integer in the nested list.
• `boolean hasNext()` Returns `true` if there are still some integers in the nested list and `false` otherwise.

#### Examples:

Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: nestedList = [1,[4,]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

#### Constraints:

• `1 <= nestedList.length <= 500`
• The values of the integers in the nested list is in the range `[-10^6, 10^6]`.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This problem is fairly straightforward, as long as we pay attention to the behavior of the NestedInteger class.

It is easiest to apply our flattening method (flatten()) during the class construction process, so that we only ever store the flattened list (data) in our class instance. Since there can be multiple layers of nesting, we should make flatten a recursive function.

With flatten, we should iterate through the given list and if the current element (el) is an integer we should push its contained value onto data, otherwise we should recursively call flatten on the nested list contained in el.

Once our data is successfully flattened, next() should be as easy as removing and returning the lead element of data. When data is reduced to a length of 0, then hasNext() can return false.

#### Implementation:

There are only minor differences between the code for all four languages.

#### Javascript Code:

``````class NestedIterator {
constructor(nestedList) {
this.data = []
this.flatten(nestedList)
};

flatten(list) {
for (let el of list)
if (el.isInteger()) this.data.push(el.getInteger())
else this.flatten(el.getList())
};

hasNext() { return this.data.length };

next() { return this.data.shift() };
};
``````

#### Python Code:

``````class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.data = []
self.flatten(nestedList)

def flatten(self, lst):
for el in lst:
if el.isInteger(): self.data.append(el.getInteger())
else: self.flatten(el.getList())

def hasNext(self) -> bool: return len(self.data)

def next(self) -> int: return self.data.pop(0)
``````

#### Java Code:

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

public NestedIterator(List<NestedInteger> nestedList) {
flatten(nestedList);
}

public void flatten(List<NestedInteger> list) {
for (NestedInteger el : list)
else flatten(el.getList());
}

public Integer next() { return data.poll(); }

public boolean hasNext() { return data.size() > 0; }
}
``````

#### C++ Code:

``````class NestedIterator {
queue<int> data;

public:
NestedIterator(vector<NestedInteger> &nestedList) {
flatten(nestedList);
}

void flatten(vector<NestedInteger> &list) {
for (NestedInteger el : list)
if (el.isInteger()) data.push(el.getInteger());
else flatten(el.getList());
}

int next() {
int res = data.front(); data.pop();
return res;
}

bool hasNext() { return data.size() > 0; }
};
``````