Python solution with detailed explanation


  • 0
    G

    Solution

    Flatten Nested List Iterator https://leetcode.com/problems/flatten-nested-list-iterator/

    • We maintain a stack st which has a tuple as (lst, idx).
    • The invariant we maintain here is that top of the stack has lst, idx such that lst[idx] is the next interger. Therefore we need some initialization (prior) to first call to next() and then we need some work to maintain the invariant after a call to every next().
    • next() - returns the interger pointed by top of stack.
    • Look at the code for more details.
    class NestedIterator(object):
        def __init__(self, nestedList):
            """
            Initialize your data structure here.
            :type nestedList: List[NestedInteger]
            """
            self.st = [[nestedList, 0]]
            self.arrange()
            
    
        def arrange(self):
            while self.st:
                lst, idx = self.st[-1][0], self.st[-1][1]
                if len(lst) == idx:
                    self.st.pop()
                elif lst[idx].isInteger() == False:
                    self.st[-1][1] += 1 # Important - move the current list index before pushing the new list.
                    self.st.append([lst[idx].getList(), 0])
                else:
                    break
            return
        
        def next(self):
            """
            :rtype: int
            """
            lst, idx = self.st[-1][0], self.st[-1][1]
            result = lst[idx].getInteger()
            self.st[-1][1] += 1
            self.arrange()
            return result
            
    
        def hasNext(self):
            """
            :rtype: bool
            """
            return bool(len(self.st))
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.