Solution: Flatten Nested List Iterator
Tags: algorithms, javascript, java, cpp
Published: 2021-04-13 09:33:39

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/flatten-nested-list-iterator/discuss/1156268).*

---

#### [Leetcode Problem #341 (*Medium*): Flatten Nested List Iterator](https://leetcode.com/problems/flatten-nested-list-iterator/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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,[6]]]
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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
public class NestedIterator implements Iterator<Integer> {
    Queue<Integer> data = new LinkedList<>();

    public NestedIterator(List<NestedInteger> nestedList) { 
        flatten(nestedList);
    }
    
    public void flatten(List<NestedInteger> list) {
        for (NestedInteger el : list)
            if (el.isInteger()) data.add(el.getInteger());
            else flatten(el.getList());
    }

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

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

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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; }
};
```