Flatten List

Solution

Both solutions take linear time and space.

Recursion

def flatten(self, nestedList):
    res = []
    def helper(nestedList):
        for item in nestedList:
            if isinstance(item, list):
                helper(item)
            else:
                res.append(item)
    helper(nestedList)
    return res

Iteration w/ Stack

def flatten(self, nestedList):
    stack = [nestedList]
    res = []
    while stack:
        top = stack.pop()
        if isinstance(top, list):
            stack.extend(reversed(top))
        else:
            res.append(top)
    return res