C++ solution using recursion


  • 1
    A
    class NestedIterator {
        const vector<NestedInteger> &vec;
        int indx;
        int nextVal;
        NestedIterator *child;
    public:
        NestedIterator(const vector<NestedInteger> &nestedList) : vec(nestedList), indx(0), child(0) {
    
        }
    
        int next() {
            if (child)
                return child->next();
            return nextVal;
        }
    
        bool hasNext() {
            if (child) {
                if (child->hasNext())
                    return true;
                delete child;
                child = 0;
            }
            
            if (indx == vec.size())
                return false;
                
            if (vec[indx].isInteger()) {
                nextVal = vec[indx++].getInteger();
                return true;
            }
            child = new NestedIterator(vec[indx++].getList());
            return hasNext();
        }
    };

  • 0
    A

    Above c++ solution takes 28 ms. Exact same solution in Java takes only 8 ms. Crazy !

    public class NestedIterator implements Iterator<Integer> {
        private List<NestedInteger> vec;
        private Integer indx;
        private Integer nextVal;
        private NestedIterator child;
        public NestedIterator(List<NestedInteger> nestedList) {
            vec = nestedList;
            indx = 0;
            child = null;
        }
    
        @Override
        public Integer next() {
            if (child != null)
                return child.next();
            return nextVal;
        }
    
        @Override
        public boolean hasNext() {
             if (child != null) {
                if (child.hasNext())
                    return true;
                child = null;
            }
            
            if (indx == vec.size())
                return false;
                
            if (vec.get(indx).isInteger()) {
                nextVal = vec.get(indx++).getInteger();
                return true;
            }
            child = new NestedIterator(vec.get(indx++).getList());
            return hasNext();
        }
    }
    

  • 0
    I

    I have the very similar approach except:

    • use iterator instead of indx
    • don't store the next val:
    • loop in hasNext() instead of recursively calling itself
    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) : m_nestedList(nestedList) {
            m_itr = m_nestedList.begin();
        }
    
        int next() {
            if (m_nestedItr) { return m_nestedItr->next(); }
            return m_itr++->getInteger();
        }
    
        bool hasNext() {
            while (true)
            {
                if (m_nestedItr)
                {
                    if (m_nestedItr->hasNext()) { return true; }
                    else { delete m_nestedItr; m_nestedItr = nullptr; }
                }
    
                if (m_itr != m_nestedList.end())
                {
                    if (!m_itr->isInteger())
                    {
                        m_nestedItr = new NestedIterator(m_itr++->getList());
                    }
                    else
                    {
                        return true;
                    }
                }
                else
                {
                    return false;
                }
            }
        }
    
    private:
        vector<NestedInteger>& m_nestedList;
        vector<NestedInteger>::iterator m_itr;
        NestedIterator* m_nestedItr = nullptr;
    };
    
    

Log in to reply
 

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