Left-to-right, O(h) space solution


  • 0
    B

    The idea is to maintain a curr NestedInteger variable. The invariant is that after every next() call, curr is:

    1. a NestedInteger where isInteger() is true or
    2. the end of the root NestedInteger

    On initialization, we try to find the first non-list NestedInteger. We maintain a stack while looking for it so that we can go "up" if we're unsuccessful in our downward DFS.

    On next(), we get the value we want, then move our index in the current list forward and do the same down-and-up DFS until we find a non-list NestedInteger.

    class NestedIterator(object):
        def __init__(self, nestedList):
            self.s = []
            self.curr = nestedList
            self.i = 0
            self.progress()
    
        def next(self):
            val = self.curr[self.i].getInteger()
            self.i += 1
            self.progress()
            return val
    
        def hasNext(self):
            return self.i < len(self.curr)
            
        def progress(self):
            curr = self.curr
            i = self.i
            s = self.s
            while i < len(curr) and not curr[i].isInteger() or s and i == len(curr):
                while i < len(curr) and not curr[i].isInteger():
                    s.append([curr, i])
                    curr = curr[i].getList()
                    i = 0
                while s and i == len(curr):
                    curr, i = s.pop()
                    i += 1
            self.curr = curr
            self.i = i
    

Log in to reply
 

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