Problem statement

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

Solution

There are a lot of different approaches, how you can solve this problem, starting with stack and ending with generators.

Here I choose not very smart, but easy to code way: I used deque.

  1. First, we put all our nestedList structure to deque.
  2. I use function FixDeque, which pop the left element from deque and put all elements of this nested list back to the left of our deque in opposite order.
  3. Function next will look at first element of deque. If it is integer, we pop it and return in, in opposite case we fix our deque first and then run function recursively.
  4. Function hasNext will try to fix our deque first if it needed to be fix and then check if it is empty or not.

Complexity

Time complexity potentially O(n+k), where k is number of brackets and n is number of numbers. Space complexity is the same.

Code

class NestedIterator:
    def __init__(self, nestedList):
        self.deq = deque(nestedList)
                        
    def FixDeque(self):
        last = self.deq.popleft()
        for e in last.getList()[::-1]:
            self.deq.appendleft(e)
        
    def next(self):
        first = self.deq[0]
        if first.isInteger():
            self.deq.popleft()
            return first.getInteger()
        else:
            self.FixDeque()
            return self.next()
    
    def hasNext(self):
        while self.deq and not self.deq[0].isInteger():
            self.FixDeque()
        return self.deq