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.

---

Leetcode Problem #341 (Medium): Flatten Nested List Iterator

---

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,[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:

(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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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; }
};

Comments

[Yuri Filatov]

This is a really good article, thanks.