341. Flatten Nested List Iterator LeetCode Solution

In this guide, you will get 341. Flatten Nested List Iterator LeetCode Solution with the best time and space complexity. The solution to Flatten Nested List Iterator problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Flatten Nested List Iterator solution in C++
4. Flatten Nested List Iterator solution in Java
5. Flatten Nested List Iterator solution in Python
6. Additional Resources

Problem Statement of Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:

NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

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].

Constraints:

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-106, 106].

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

341. Flatten Nested List Iterator LeetCode Solution in C++

class NestedIterator {
 public:
  NestedIterator(vector<NestedInteger>& nestedList) {
    addInteger(nestedList);
  }

  int next() {
    const int num = q.front();
    q.pop();
    return num;
  }

  bool hasNext() {
    return !q.empty();
  }

 private:
  queue<int> q;

  void addInteger(const vector<NestedInteger>& nestedList) {
    for (const NestedInteger& ni : nestedList)
      if (ni.isInteger())
        q.push(ni.getInteger());
      else
        addInteger(ni.getList());
  }
};
/* code provided by PROGIEZ */

341. Flatten Nested List Iterator LeetCode Solution in Java

public class NestedIterator implements Iterator<Integer> {
  public NestedIterator(List<NestedInteger> nestedList) {
    addInteger(nestedList);
  }

  @Override
  public Integer next() {
    return q.poll();
  }

  @Override
  public boolean hasNext() {
    return !q.isEmpty();
  }

  private Queue<Integer> q = new ArrayDeque<>();

  private void addInteger(final List<NestedInteger> nestedList) {
    for (final NestedInteger ni : nestedList)
      if (ni.isInteger())
        q.offer(ni.getInteger());
      else
        addInteger(ni.getList());
  }
}
// code provided by PROGIEZ

341. Flatten Nested List Iterator LeetCode Solution in Python

class NestedIterator:
  def __init__(self, nestedList: list[NestedInteger]):
    self.q = collections.deque()
    self.addInteger(nestedList)

  def next(self) -> int:
    return self.q.popleft()

  def hasNext(self) -> bool:
    return self.q

  def addInteger(self, nestedList: list[NestedInteger]) -> None:
    for ni in nestedList:
      if ni.isInteger():
        self.q.append(ni.getInteger())
      else:
        self.addInteger(ni.getList())
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.