LeetCode 341: Flatten Nested List Iterator Solution

Master LeetCode problem 341 (Flatten Nested List Iterator), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

341. Flatten Nested List Iterator

Medium

Stack Tree Depth-First Search Design Queue Iterator

Problem Explanation

Explanation

To flatten a nested list iterator, we can use a stack to keep track of the nested elements while iterating over them. We will implement the NestedIterator class with the required next() and hasNext() methods to iterate over the flattened list of integers.

Algorithm:

Initialize a stack to store the nested elements.
Implement a helper method to recursively flatten the nested list and push the elements onto the stack.
In the constructor of NestedIterator, flatten the nested list using the helper method and push the elements onto the stack in reverse order.
Implement the next() method to return the next integer in the flattened list.
Implement the hasNext() method to check if there are still integers in the flattened list.
If hasNext() returns true, keep returning integers using next() until the end.

Time Complexity:

The constructor will have a time complexity of O(n), where n is the total number of elements in the nested list.
The next() and hasNext() methods will have an average time complexity of O(1) for each call.

Space Complexity:

The space complexity will be O(n) to store the nested elements in the stack.

Solution Code

import java.util.*;

public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        flattenList(nestedList);
    }

    private void flattenList(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) {
                return true;
            }
            flattenList(stack.pop().getList());
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 341 (Flatten Nested List Iterator)?

This page provides optimized solutions for LeetCode problem 341 (Flatten Nested List Iterator) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 341 (Flatten Nested List Iterator)?

The time complexity for LeetCode 341 (Flatten Nested List Iterator) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 341 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 341 in Java, C++, or Python.

Back to LeetCode Solutions