341. Flatten Nested List Iterator - Explanation

1. Recursion (Flatten And Store Into Global List )

class NestedIterator:
    def __init__(self, nestedList):
        self.arr = []
        self.ptr = 0
        self.dfs(nestedList)

    def next(self):
        val = self.arr[self.ptr]
        self.ptr += 1
        return val

    def hasNext(self):
        return self.ptr < len(self.arr)

    def dfs(self, nestedArr):
        for num in nestedArr:
            if num.isInteger():
                self.arr.append(num.getInteger())
            else:
                self.dfs(num.getList())

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

2. Recursion (Flatten And Return)

class NestedIterator:
    def __init__(self, nestedList):
        self.arr = self.dfs(nestedList)
        self.ptr = 0

    def dfs(self, nestedArr):
        res = []
        for num in nestedArr:
            if num.isInteger():
                res.append(num.getInteger())
            else:
                res.extend(self.dfs(num.getList()))
        return res

    def next(self):
        val = self.arr[self.ptr]
        self.ptr += 1
        return val

    def hasNext(self):
        return self.ptr < len(self.arr)

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

3. Recursion + Stack

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        self.dfs(nestedList)
        self.stack.reverse()

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

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

    def dfs(self, nested):
        for num in nested:
            if num.isInteger():
                self.stack.append(num.getInteger())
            else:
                self.dfs(num.getList())

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

4. Stack

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = nestedList
        self.stack.reverse()

    def next(self) -> int:
        return self.stack.pop().getInteger()

    def hasNext(self) -> bool:
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True

            self.stack.pop()
            self.stack.extend(reversed(top.getList()))
        return False

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n)$

Where $n$ is the number of integers and $d$ is the nesting depth.