341. Flatten Nested List Iterator - cocoder39/coco39_LC GitHub Wiki

341. Flatten Nested List Iterator

python generator based solution

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.__generator = self.__int_generator(nestedList)
        self._peeked = None
        self.__advance()
    
    def __int_generator(self, nestedList: [NestedInteger]) -> "Generator[int]":
        for ni in nestedList:
            if ni.isInteger():
                yield ni.getInteger()
            else:
                yield from self.__int_generator(ni.getList())
    
    def __advance(self):
        try:
            self._peeked = next(self.__generator)
        except StopIteration:
            self._peeked = None
        
    
    def next(self) -> int:
        if self._peeked is None:
            raise StopIteration('No more element')

        result = self._peeked
        self.__advance()
        return result

        
    def hasNext(self) -> bool:
        return self._peeked is not None

================

2020 Notes:

Time complexity: suppose N is #integers and L is #list and D is the maximum nesting depth (maximum number of lists inside each other). Each integer will go through if brach once and each list will go through else branch once. As D is smaller than L, so total time complexity is O(N + L).

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        def flatten_list(nestedList):
            for ni in nestedList:
                if ni.isInteger():
                    self._integers.append(ni.getInteger())
                else:
                    flatten_list(ni.getList())
                
        self._integers = []
        self._index = 0
        flatten_list(nestedList)
        
    def next(self) -> int:
        res = self._integers[self._index]
        self._index += 1
        return res
        
    def hasNext(self) -> bool:
        return self._index < len(self._integers)

Option 2: iterative

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for i in range(len(nestedList)-1, -1, -1):
            self.stack.append(nestedList[i])
            
    
    def next(self) -> int:
        nestedList = self.stack.pop()
        return nestedList.getInteger()
        
    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            nestedList = self.stack.pop().getList()    
            for i in range(len(nestedList)-1, -1, -1):
                self.stack.append(nestedList[i])
        
        return self.stack and self.stack[-1].isInteger()

===============================================================

auto cur_it = begins.top();
                if (cur_it->isInteger()) {
                    return true;
                }
                begins.top()++;
                begins.push(cur_it->getList().begin());
                ends.push(cur_it->getList().end());

above is the most essential part. check if the iterator points to an integer. if not, the iterator must point to a list. then replace the iterator with its next iterator within the list and push the iterator of its sublist into the stack.

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        begins.push(nestedList.begin());
        ends.push(nestedList.end());
    }

    int next() {
        hasNext();
        auto cur_it = begins.top();
        begins.top()++;
        return cur_it->getInteger();
    }

    bool hasNext() {
        while (! begins.empty()) {
            if (begins.top() == ends.top()) {
                begins.pop();
                ends.pop();
            }
            else {
                auto cur_it = begins.top();
                if (cur_it->isInteger()) {
                    return true;
                }
                begins.top()++;
                begins.push(cur_it->getList().begin());
                ends.push(cur_it->getList().end());
            }
        }
        return false;
    }
private:
    stack<vector<NestedInteger>::iterator> begins;
    stack<vector<NestedInteger>::iterator> ends;
};

finding all leaves of a tree push items in vector into stack reversely. O(h) memory for stack where h is # of levels/ height of tree. visiting each node twice, total time for flattening is O(N1) where N1 is # of nodes not # of leaves. amortized time for hasNext() is O(N1/N2) where N2 is # of leaves, worst case for hasNext() is O(N1)

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        int sz = nestedList.size();
        for (int i = sz - 1; i >= 0; i--) {
            st.push(nestedList[i]);
        }
    }

    int next() {
        auto& res = st.top();
        st.pop();
        return res.getInteger();
    }

    bool hasNext() {
        while (! st.empty()) {
            auto ni = st.top(); 
            if (ni.isInteger()) {
                return true;
            } else {
                st.pop();
                auto& nilist = ni.getList();
                int sz = nilist.size();
                for (int i = sz - 1; i >= 0; i--) {
                    st.push(nilist[i]);
                }
            }
        }
        return false;
    }
private:
    stack<NestedInteger> st;
};

a naive solution stores all data at initialization. O(1) time and O(N) memory where N is # integer

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

    int next() {
        return res[idx++];
    }

    bool hasNext() {
        return idx < res.size();
    }
private:
    vector<int> res;
    int idx = 0;
    
    void helper(vector<NestedInteger> &nestedList) {
        for (auto &ni : nestedList) {
            if (ni.isInteger()) {
                res.push_back(ni.getInteger());
            } else {
                helper(ni.getList());
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️