[LeetCode] 341. Flatten Nested List Iterator

 Problem : https://leetcode.com/problems/flatten-nested-list-iterator/

Use stack to cache the expanded lists.

Must filter out the empty nested lists in hasNext() method.

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

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
        
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            # expand non-empty nested list
            nestedList = self.stack.pop().getList()
            if nestedList:
                for n in reversed(nestedList):
                    self.stack.append(n)

        return self.stack
         

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

Another approach of using stack. It's similar to how compiler maintains call-stack.

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

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = [[nestedList, 0]]
    
    def next(self) -> int:
        nlist, nindex = self.stack[-1]
        
        self.stack[-1][1] += 1
        return nlist[nindex].getInteger()
        
    
    def hasNext(self) -> bool:     
        while self.stack:
            nlist, nindex = self.stack[-1]

            if nindex == len(nlist):
                self.stack.pop()
                continue

            if nlist[nindex].isInteger():
                break

            self.stack[-1][1] += 1
            childList = nlist[nindex].getList()
            if childList:
                self.stack.append([childList, 0])
        
        return self.stack
         

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

Edited on 04/13/2021. Add the second stack based approach.