Evolve from intuition to optimal, a review of top solutions


  • 2
    1. O(n) space, Flatten the list in constructor. The nested list can be visualized as a tree and the iterator order is dfs.
    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            dfs(nestedList); 
        }
        void dfs(vector<NestedInteger> &nestedList) {
             for(int i=nestedList.size()-1;i>=0;i--)
                if(nestedList[i].isInteger()) stk.push(nestedList[i].getInteger());
                else dfs(nestedList[i].getList());
        }
        int next() {
            int nxt = stk.top();
            stk.pop();
            return nxt;
        }
        bool hasNext() {
            return !stk.empty();
        }
    private:
        stack<int> stk;
    };
    
    1. O(n) space, Flatten the list as you go. #1 is not an iterator because an iterator should never copy the data structure. Besides, it is a waste of time to flatten and store the whole list if we may only visit a few elements. So we can store the first level in the stack and flatten it as we go. If the list is flat, then there is no saving over #1.
    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            for(int i=nestedList.size()-1;i>=0;i--) stk.push(&nestedList[i]);
        }
        int next() {
            int nxt = stk.top()->getInteger();
            stk.pop();
            return nxt;
        }
        bool hasNext() {
            while(!stk.empty()) {
                NestedInteger *p = stk.top();
                if(p->isInteger()) return 1;
                vector<NestedInteger> &vec = p->getList();
                stk.pop();
                for(int i=vec.size()-1;i>=0;i--) stk.push(&vec[i]);
            }
            return 0;
        }
    private:
        stack<NestedInteger*> stk;
    };
    
    1. O(h) space, Real iterator. #2 stores pointers to each element in the current list. This still can be large. The following solution only stores 2 iterators of the current list. The great idea is from @StefanPochmann. h is the depth of the list.
    class NestedIterator {
    public:
        typedef vector<NestedInteger>::iterator iter;  
        NestedIterator(vector<NestedInteger> &nestedList) {
            begins.push(nestedList.begin());
            ends.push(nestedList.end());
        }
        int next() {
            return begins.top()++->getInteger();
        }
        bool hasNext() {
            while(!begins.empty()) {
                iter it = begins.top();
                if(it == ends.top()) {
                    begins.pop();
                    ends.pop();
                    if(!begins.empty()) begins.top()++;
                } else if (it->isInteger()) return 1;
                else {
                    vector<NestedInteger>& lst = it->getList();
                    begins.push(lst.begin());
                    ends.push(lst.end());
                }
            }
            return 0;
        }
    private:
       stack<iter> begins, ends;
    };
    

Log in to reply
 

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