C++ solution, using O(1) space, without explicit recursion or flattening the vector


  • 0
    G

    See detailed explanations embedded in the code.

    Running time (to this date) is 32ms.

    The implicit recursion is upon advancing, when creating the next iterator (which in turn could creating next iterators of its own)

    class NestedIterator {
        vector<NestedInteger> &_nestedList;
        
        // the following two members represents the next element
        // at all times, the following conditions are met:
        // 1. if _nextIndex greater-than-or-equal to _nestedList.size(), there's no next element
        // 2. otherwise, the next element is at _nestedList[_nextIndex], whether it's a list or an integer
        // 3. if _nextIndex points to an integer, _nextIterator is not nullptr, and the iterator is valid, while "hasNext" is true
        int _nextIndex;
        unique_ptr<NestedIterator> _nextIterator;
        
    public:
        NestedIterator(vector<NestedInteger> &nestedList): _nestedList(nestedList) {
            _nextIndex = -1;
            advance();
        }
    
        int next() {
            // if hasNext is 'false' behavior is undefined, so we assumed the next element is valid
            auto& next = _nestedList[_nextIndex];
            // get the next element (either by quering the current element or the iterator)
            auto res = next.isInteger() ? next.getInteger() : _nextIterator->next();
            // _nextIterator was already updated by calling the next() above. We need to make sure our indices points to a valid next
            advance();
            return res;
        }
    
        bool hasNext() {
            return _nextIndex < _nestedList.size();
        }
        
    private:
        // assumed the current position, represented by _nextIndex and _nextIterator, has been consumed, 
        // and we are interested in advancing to the next available element
        void advance() {
            // if the current element is a nested list, and the nested iterator determines there's a next element return
            if (_nextIterator && _nextIterator->hasNext()) return;
    
            // otherwise, we need to skip to the next element
            do {
                _nextIndex++;
                // if we are passed the end of the vector, or the next element is an integer, nullify the iterator
                // otherwise, create an iterator of the next nested list
                _nextIterator = (_nextIndex >= _nestedList.size() || _nestedList[_nextIndex].isInteger()) 
                    ? nullptr 
                    : make_unique<NestedIterator>(_nestedList[_nextIndex].getList());
            } while (_nextIterator && !_nextIterator->hasNext());
            
            // if finished the loop, once these things conditions are met:
            // 1. we reached to the end of the vector, thus nextIterator was nullified and _nextIndex == _nestedList.size()
            // 2. we reached to an element that's an integer, so nextIterator was nullified and _nestedList[_nextIndex].isInteger() == true
            // 3. we reached to an element that's a nested list, so nextIterator is an iterator for that list, and _nextIndex points to that element
        }
        
        // standard implementation of make_unique using forwarding references and variadic templates
        template <typename T, typename... Ts>
        unique_ptr<T> make_unique(Ts&&... args) {
            return unique_ptr<T>(new T(std::forward<Ts>(args)...));
        }
    };

  • 0

    why do you think your code is O(1) space? you still save a copy of nestedList. All the other method using vector < int> to save the data uses the same space.


  • 0
    G

    I'm saving the reference. There's the iterator space and the recursion


  • 0
    M

    It's a little hard to understand TOT


Log in to reply
 

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