Speed-Memory tradeoff


  • 0
    F
    vector<int> _levelIdx;
    vector<NestedInteger> &_rootNl;
    NestedIterator(vector<NestedInteger> &nestedList) : _rootNl(nestedList) {
        _levelIdx.push_back(0);
        validateNext(_rootNl, 0);
    }
    
    bool validateNext(const vector<NestedInteger> &nl, int level) 
    {
        //add this level if it doesn't exist
        if(level == _levelIdx.size()) _levelIdx.push_back(0);
    
        for(int i = _levelIdx[level]; i < nl.size(); ++i) {
            if(nl[i].isInteger() || validateNext(nl[i].getList(), level+1)) {
                _levelIdx[level] = i;
                return true;
            }
        }
        _levelIdx.pop_back();   // pop this level as no valid next value
        return false;
    }
    
    int getValue(const vector<NestedInteger> &nl, int level)
    {
        if(level == _levelIdx.size()-1) return nl[_levelIdx[level]].getInteger();
        return getValue(nl[_levelIdx[level]].getList(), level+1);
    }
    
    int next() {
        int nextValue = getValue(_rootNl, 0);
        _levelIdx[_levelIdx.size()-1]++;
        validateNext(_rootNl, 0);
        return nextValue;
    }
    
    bool hasNext() {
       return (!_levelIdx.empty()); 
    }

Log in to reply
 

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