C++ solution using a stack with explanation


  • 0
    G
    1. Use a stack to keep track of elements in the given NestedInteger object
    2. Top element in the stack must always be an integer that the function next() can return instantly in O(1)
    3. If top element in the stack is not an integer object, then it must be a list object. Keep flattening this list object to the deepest level (see function flattenList in the code). This check is done in the hasNext() function, which does most of the heavy lifting.

    Alternatively, one could use a stack<NestedInteger*> instead of stack<NestedInteger> to avoid making copy of each object. I chose to keep the code simpler and more readable for both Java and C++ users.

    class NestedIterator {
    private:
        stack<NestedInteger> st;
    
        //Function to flatten list to integer values 
        void flattenList(NestedInteger& obj) {
            //If a list, flatten it from end to front
            if (!obj.isInteger()) {
                vector<NestedInteger>& vec = obj.getList();
                for (auto it=vec.rbegin(); it!=vec.rend(); it++) {
                    flattenList(*it);
                }
            } 
            else {
                st.push(obj);
            }
        }
    
    public:
        //Constructor
        NestedIterator(vector<NestedInteger> &nestedList) {
            //Add objects from end to front into the stack
            for (auto it=nestedList.rbegin(); it!=nestedList.rend(); it++) {
                st.push(*it);
            }
        }
    
        int next() {
            int val = st.top().getInteger();
            st.pop();
            return val;
        }
    
        bool hasNext() {   
            //Until the next object to return is not an integer, keep flattening the list
            while (!st.empty() && !st.top().isInteger()) {
                NestedInteger obj = st.top();
                st.pop();
                flattenList(obj);
            }
            //This is to make sure that the recently flattened list wasn't empty (for example: [[]])
            return !st.empty();
        }
    };
    

Log in to reply
 

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