C++ 29ms 17 lines using iterators with comments


  • 0

    Using a stack to keep track of all iterator candidates. The trick is keeping st.top() a valid integer iterator:

    class NestedIterator {
    private:
        stack<pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator>> st;
        
        void update() {                             // make sure st.top().first is pointing to a valid integer
            while (st.size() && (st.top().first == st.top().second || !st.top().first->isInteger())) {
                if (st.top().first == st.top().second) {
                    st.pop();                       // if st.top() is invalid, pop it out
                } else {
                    auto cur = st.top().first++;    // if st.top() is a nested list, dive into it
                    st.push(make_pair(cur->getList().begin(), cur->getList().end()));
                }
            }
        }
        
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            st.push(make_pair(nestedList.begin(), nestedList.end()));
            update();                               // initialize the stack
        }
    
        int next() {
            int val = (st.top().first++)->getInteger();
            update();
            return val;
        }
    
        bool hasNext() {
            return st.size();                       // since stack.top() is always a valid interger, hasNext if stack is not empty
        }
    };
    

Log in to reply
 

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