341

341. Flatten Nested List Iterator (Medium)

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.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

 

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 [-106, 106].

Companies: Yandex, Netflix, Apple, Bloomberg, LinkedIn, Airbnb, Facebook, Uber, Twitter, Amazon, Google, Salesforce, Microsoft, Adobe, Accolite, Coinbase, Workday, instabase

Related Topics:
Stack, Tree, Depth-First Search, Design, Queue, Iterator

Similar Questions:

• Flatten 2D Vector (Medium)
• Zigzag Iterator (Medium)
• Mini Parser (Medium)
• Array Nesting (Medium)

Solution 1.

• Preprocess the list in the constructor, and store all the numbers in an array vals
• In next and hasNext, we just traverse the array vals

// OJ: https://leetcode.com/problems/flatten-nested-list-iterator
// Author: github.com/lzl124631x
// Time:
//      NestedIterator: O(N)
//      next, hasNext: O(1)
// Space: O(N)
class NestedIterator {
    vector<int> vals;
    int i = 0;
public:
    NestedIterator(vector<NestedInteger> &list) {
        deque<NestedInteger> q{begin(list), end(list)};
        while (q.size()) {
            auto i = q.front();
            q.pop_front();
            if (i.isInteger()) {
                vals.push_back(i.getInteger());
            } else {
                auto L = i.getList();
                for (auto it = L.rbegin(); it != L.rend(); ++it) q.push_front(*it);
            }
        }
    }
    int next() {
        return vals[i++];
    }
    bool hasNext() {
        return i < vals.size();
    }
};

Solution 2.

Use a stack to store the current and end iterators at each level.

// OJ: https://leetcode.com/problems/flatten-nested-list-iterator/
// Author: github.com/lzl124631x
// Time: 
//      NestedInteger, next: O(1) amortized
//      hasNext: O(1)
// Space: O(D) where D is the max depth of the list
class NestedIterator {
    typedef vector<NestedInteger>::iterator iter;
    stack<pair<iter, iter>> s;
    void goToInteger() {
        while (s.size()) {
            if (s.top().first == s.top().second) {
                s.pop();
                if (s.size()) s.top().first++;
            } else if (s.top().first->isInteger()) break;
            else {
                auto &list = s.top().first->getList();
                s.emplace(list.begin(), list.end());
            }
        }
    }
public:
    NestedIterator(vector<NestedInteger> &list) {
        s.emplace(list.begin(), list.end());
        goToInteger();
    }
    int next() {
        int val = s.top().first->getInteger();
        s.top().first++;
        goToInteger();
        return val;
    }
    bool hasNext() {
        return s.size();
    }
};

Solution 3.

Similar to solution 1, but instead of generating every number in constructor, we store the NestedIntegers in a stack, and stop filling the stack once we've found an integer.

// OJ: https://leetcode.com/problems/flatten-nested-list-iterator/
// Author: github.com/lzl124631x
// Time: O(1) amortized
// Space: O(N)
class NestedIterator {
    stack<NestedInteger> s;
    void goToInteger() {
        while (s.size() && !s.top().isInteger()) {
            auto list = s.top().getList();
            s.pop();
            for (int i = list.size() - 1; i >= 0; --i) s.push(list[i]);
        }
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; --i) s.push(nestedList[i]);
        goToInteger();
    }
    int next() {
        int val = s.top().getInteger();
        s.pop();
        goToInteger();
        return val;
    }
    bool hasNext() {
        return s.size();
    }
};