C++ Real "Nested" Iterator, Without Explicit Stack, 29ms


  • 0
    W

    There are many excellent solutions, which are generally either "queue" based or "stack" based. The "queue" method stores all data while initializing the NestedIterator, so it is not real iterator. The "stack" based method uses real iterator, but not real "Nested" iterator. In my solution, I do not explicitly use any stack or queue. Instead, I keep two iterators, one pointing to the current NestedInteger, another pointing to the end of the given vector. Besides, I keep a nested pointer of NestedIterator class itself, which points to a NestedInteger that is not a single integer. Here is my private member variables:

    private:
        vector<NestedInteger>::iterator endIter; // pointing to the end of given vector.
        vector<NestedInteger>::iterator curIter; // pointing to the current NestedInteger.
        NestedIterator *iter; // pointing to a NestedInteger that is not a single integer.
        int rtValue; // stores the value that is about to be returned by next().
        int alreadyFound; // indicates whether a value is found by the last call of hasNext().     
    

    The key function of my NestedIterator class is hasNext(). The general idea is that a) when the current NestedInteger is a single integer, we just record it for next(); b) when the current NestedInteger is not a single integer, we create a new NestedIterator that points to the list stored in current NestedInteger.
    Note that it is actually a DFS idea. But as long as we find an integer value, we record it and stop going deeper in recursion. So the space complexity should be the same with "stack" based method, namely O(h), where h is the largest depth of input data structure. The time complexity of hasNext() should be O(h) also, and the worst case happens when the input data structure is continuously nested towards the deepest nest.

    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            curIter = nestedList.begin();
            endIter = nestedList.end();
            alreadyFound = false;
            iter = NULL;
        }
    
        int next() {
            alreadyFound = false;
            return rtValue;
        }
    
        bool hasNext() {
            if(alreadyFound) return true;
            if(iter && iter->hasNext()) {
                rtValue = iter->next();
                alreadyFound = true;
                return true;
            }
            if(curIter == endIter) return false;
            while(!alreadyFound && curIter != endIter) {
                if(curIter->isInteger()) {
                    rtValue = curIter->getInteger();
                    alreadyFound = true;
                }
                else {
                    iter = new NestedIterator(curIter->getList());
                    while(!alreadyFound && iter->hasNext()) {
                        rtValue = iter->next();
                        alreadyFound = true;
                    }
                }
                curIter++;
            }
            return alreadyFound;    
        }
    
    private:
        vector<NestedInteger>::iterator endIter;
        vector<NestedInteger>::iterator curIter;
        int rtValue;
        int alreadyFound;
        NestedIterator *iter;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.