C++ simple O(n) time complexity non-recursive solution using deque


  • 0

    O(n): n here is the total number of actual integer.

    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            for(auto nl: nestedList)
                dq.push_back(nl);
        }
    
        int next() {
            NestedInteger NI = dq.front();
            dq.pop_front();
            return NI.getInteger();
        }
    
        bool hasNext() {
            while(dq.size() && !dq.front().isInteger()){
                NestedInteger front = dq.front();
                dq.pop_front();
                vector<NestedInteger> nls = front.getList();
                for(int i = nls.size() - 1; i >= 0; i--){
                    dq.push_front(nls[i]);
                }
            }
            
            if(dq.size() && dq.front().isInteger()) return true;
            return false;
        }
        
    private: 
        deque<NestedInteger> dq;
    };

Log in to reply
 

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