341. Flatten Nested List Iterator – Leetcode Solutions

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        # Use a stack to simulate the recursion and flatten the list
        self.stack = nestedList[::-1]  # Initialize the stack with the reversed nested list
    
    def next(self) -> int:
        # Assuming that hasNext has already been called to ensure there is a next integer
        return self.stack.pop().getInteger()  # Pop the top element and return the integer
    
    def hasNext(self) -> bool:
        # Loop until we find an integer on top of the stack or the stack is empty
        while self.stack:
            top = self.stack[-1]  # Peek at the top element of the stack
            if top.isInteger():  # If the top element is an integer, we are ready for next()
                return True
            else:
                # The top element is a list, pop it and push its contents onto the stack
                self.stack.pop()
                self.stack.extend(top.getList()[::-1])  # Add the elements of the list in reverse order
        return False  # If stack is empty, return False

class NestedIterator {
private:
    stack<NestedInteger> st; // Stack to hold the nested structure

public:
    // Constructor that initializes the iterator with the nested list
    NestedIterator(vector<NestedInteger> &nestedList) {
        // Push all elements from the nestedList to the stack in reverse order
        // because stacks are LIFO (Last In First Out).
        // We want to process the elements in their original order.
        for (int i = nestedList.size() - 1; i >= 0; --i) {
            st.push(nestedList[i]);
        }
    }

    // Returns the next integer in the flattened list
    int next() {
        // First, ensure there is a next element available by flattening the structure
        if (!hasNext()) {
            throw runtime_error("No more elements");
        }
        // Once we have a guaranteed integer at the top of the stack, we can return it
        int result = st.top().getInteger();
        st.pop(); // Remove it from the stack
        return result;
    }

    // Returns true if there are more integers to iterate over
    bool hasNext() {
        // We need to flatten the stack until we find an integer at the top
        while (!st.empty()) {
            NestedInteger current = st.top(); // Get the current top element
            if (current.isInteger()) {
                return true; // Found an integer, stop flattening
            }
            // If it's a list, pop it and push its elements onto the stack
            st.pop(); 
            const vector<NestedInteger> &nestedList = current.getList();
            // Push the elements of the list in reverse order onto the stack
            for (int i = nestedList.size() - 1; i >= 0; --i) {
                st.push(nestedList[i]);
            }
        }
        return false; // No more integers available
    }
};

var NestedIterator = function(nestedList) {
    // Initialize a stack to simulate the recursive traversal
    // Flatten the list by reversing it to process elements from left to right
    this.stack = [];
    this.flattenList(nestedList);
};

NestedIterator.prototype.flattenList = function(nestedList) {
    // Loop through the list in reverse order to process left to right
    for (let i = nestedList.length - 1; i >= 0; i--) {
        this.stack.push(nestedList[i]);
    }
};

NestedIterator.prototype.hasNext = function() {
    // Ensure the top of the stack is an integer, flatten if necessary
    while (this.stack.length > 0) {
        let top = this.stack[this.stack.length - 1];
        // If the top of the stack is an integer, return true
        if (top.isInteger()) {
            return true;
        }
        // If the top is a list, pop it and flatten it
        this.stack.pop();
        this.flattenList(top.getList());
    }
    // No elements left
    return false;
};

NestedIterator.prototype.next = function() {
    // Since hasNext() ensures that the top is an integer, just pop and return it
    return this.stack.pop().getInteger();
};

public class NestedIterator implements Iterator<Integer> {
    // Use a stack to simulate recursion and keep track of where we are in the nested list
    private Stack<NestedInteger> stack;

    // Constructor initializes the stack with the nested list
    public NestedIterator(List<NestedInteger> nestedList) {
        // Initialize the stack and push all elements of the nested list in reverse order
        // This is done to process the first element at the top of the stack
        stack = new Stack<>();
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    // Returns the next integer in the flattened structure
    @Override
    public Integer next() {
        // Call hasNext to make sure the stack is in the correct state
        if (hasNext()) {
            return stack.pop().getInteger(); // Return the integer at the top of the stack
        }
        return null; // This case should not be reached if hasNext is used properly
    }

    // Checks if there is a next integer to return
    @Override
    public boolean hasNext() {
        // We flatten the list by processing the stack until we reach an integer
        while (!stack.isEmpty()) {
            NestedInteger top = stack.peek();
            if (top.isInteger()) {
                return true; // If the top is an integer, we are ready to return it
            } 
            // If the top is a list, pop it and push its contents in reverse order onto the stack
            stack.pop();
            List<NestedInteger> topList = top.getList();
            for (int i = topList.size() - 1; i >= 0; i--) {
                stack.push(topList.get(i));
            }
        }
        return false; // If the stack is empty, there are no more integers
    }
}