Two generalized C++ solutions: O(N_Vectors) space, O(1) time for each operation


  • 0
    X

    Whilst the first solution might seem more concise, it doesn't take care of disposing of the vectors which do not have any more elements to return - so in fact next() has O(N_Vectors) complexity there.

    The second solution is iterator-based, and both next() and hasNext() are O(1), as the fully used vectors aren't looped through.

    Both solutions are well generalized to employ an arbitrary number of vectors.

    First solution (O(N) space, O(N) time for next()):

    class ZigzagIterator {
        vector<const vector<int>*> mVectors;
        vector<size_t> mIndices;
    
        size_t mCurrentVector;
        size_t mRemaining;
    
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) : mVectors{&v1, &v2}, mIndices{0, 0}, mCurrentVector(0), mRemaining(v1.size() + v2.size()) {
            
        }
    
        int next() {
            if(!hasNext()) throw exception();
            
            while(mIndices[mCurrentVector] == mVectors[mCurrentVector]->size()) mCurrentVector = (mCurrentVector + 1) % mVectors.size();
            auto result = (*mVectors[mCurrentVector])[mIndices[mCurrentVector]];
            ++mIndices[mCurrentVector];
            mCurrentVector = (mCurrentVector + 1) % mVectors.size();
            --mRemaining;
            return result;
        }
    
        bool hasNext() {
            return (mRemaining > 0);
        }
    };
    

    Second solution, iterator-based (O(N) space, O(1) time for each operation):

    class ZigzagIterator {
        list<const vector<int>*> mVectors;
        list<size_t> mIndices;
    
        list<const vector<int>*>::iterator mCurrentVector;
        list<size_t>::iterator mCurrentIndex;
    
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) : mVectors{&v1, &v2}, mIndices{0, 0}, mCurrentVector(mVectors.begin()), mCurrentIndex(mIndices.begin()) {
            rotate();
        }
    
        void rotate()
        {
            while(mCurrentVector != mVectors.end())
            {
                if(*mCurrentIndex == (*mCurrentVector)->size()) {
                    mCurrentVector = mVectors.erase(mCurrentVector);
                    mCurrentIndex = mIndices.erase(mCurrentIndex);
                    if(mCurrentVector == mVectors.end() && !mVectors.empty())
                    {
                        mCurrentVector = mVectors.begin();
                        mCurrentIndex = mIndices.begin();
                    }
                }
                else break;
            }
        }
    
        int next() {
            if(!hasNext()) throw exception();
    
            auto result = (**mCurrentVector)[*mCurrentIndex];
            ++*mCurrentIndex;
            ++mCurrentIndex;
            if(++mCurrentVector == mVectors.end())
            {
                mCurrentVector = mVectors.begin();
                mCurrentIndex = mIndices.begin();
            }
            rotate();
            return result;
        }
    
        bool hasNext() {
            return !mVectors.empty();
        }
    };

  • 0

    That's not properly generalized, as you're cycling the vectors, not zigzagging.


Log in to reply
 

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