Flatten Nested List Iterator - Leetcode Solution

Problem Description: Implement an iterator to flatten a 2D vector. The vector consists of several nested vectors. Each nested vector can have any number of elements. The iterator should be able to work on any number of nested vectors.

Example: Input: [[1,1],2,[1,1]]

Output: [1,1,2,1,1]

Note: The input can be of any level of nesting.

Solution: An easy approach to solve the problem is to flatten the input list when initializing the iterator. In this way, we can simply work with a one-dimensional list and iterate over it without the need for nested loops. Here is the code for the iterator class:

class NestedIterator: def init(self, nestedList: [NestedInteger]): self.data = [] self.flatten(nestedList)

def flatten(self, nestedList):
    for elem in nestedList:
        if elem.isInteger():
            self.data.append(elem.getInteger())
        else:
            self.flatten(elem.getList())

def next(self) -> int:
    return self.data.pop(0)

def hasNext(self) -> bool:
    return len(self.data) > 0 

In the init method, we first initialize an empty list called self.data. Then, we call a helper function flatten that takes a nestedList as input and extracts all integers from it. We iterate over each item in the list and check if it is an integer or a nested list. If it is an integer, we append it to the self.data list. If it is a nested list, we call the flatten function recursively.

The next method simply returns the first item from the self.data list and removes it. The hasNext method checks whether the self.data list is empty or not. If it is empty, it returns False, otherwise returns True.

Sample Input: nestedList = [1,[4,[6]]]

Sample Output: iterator = NestedIterator(nestedList) print(iterator.next()) # 1 print(iterator.next()) # 4 print(iterator.next()) # 6 print(iterator.hasNext()) # False

Explanation: Here, we have a nestedList that has two nested lists inside it. We initialize a new iterator using the NestedIterator class, passing the nestedList as an argument. The output shows that the iterator returns the values in the flattened form of the input list. The hasNext method returns False when all the elements are iterated over.

1