# 341 Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

**Example 1:**\
Given the list`[[1,1],2,[1,1]]`,

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:`[1,1,2,1,1]`.

**Example 2:**\
Given the list`[1,[4,[6]]]`,

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

**The Idea:** A nestedList is nothing but a tree. Naturally, a tree is recursively traversed, but we don't have that luxiery here because call stack has to be saved, in a sense. Any nestedList can be represented as a cons cell (lisp idea). For example, the tree below represents the following list: `(1 (2 6 7 8) 3 (4 (9 12)) (5 10 11))`. As we can see, following a preorder traversal through this tree will reveal the correct order of the elements within the nested list. A preorder traversal can be accomplished iteratively using a stack.

![](/files/-LoJIrkfVMXvnhkrmH_1)

The approach to this problem is the same, except that we'll need to store an iterator for every sublist.

Any element within a nestedList can be either of two things: an integer or a list. If the element is an integer, we're ok to output it. Otherwise, if it is a list, we need to push this list onto the stack, and initialize it's own iterator (starting from 0).![](/files/-LoJIrkhkrvYOgSqwdxY)

**Complexity:** O(N) time where N is the total number of element in the list (including the nested lists), and O(|deepest nestest list|) space

```python
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.s = [[nestedList, 0]]

    def next(self):
        """
        :rtype: int
        """
        l, i = self.s[-1]
        self.s[-1][1] += 1
        return l[i].getInteger()

    def hasNext(self):
        """
        :rtype: bool
        """
        # get to the point where we can find an integer
        while self.s:
            nl, i = self.s[-1]

            # the current list is exhausted
            if i == len(nl):
                self.s.pop()

            # current admidst an iteration through nonexhausted list
            elif nl[i].isInteger():
                return True

            # otherwise next element must be a list
            # add this to the stack so we can backtrack to it later
            else:
                self.s[-1][1] += 1
                self.s.append([nl[i].getList(), 0])

        # reached back to the root, iteration is complete
        return False




        # Your NestedIterator object will be instantiated and called as such:
        # i, v = NestedIterator(nestedList), []
        # while i.hasNext(): v.append(i.next())
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/341-flatten-nested-list-iterator.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.