Flatten Nested List Iterator

Medium

Netflix

7 views

Topics:

StacksRecursion

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-10⁶, 10⁶].

Flatten Nested List Iterator

Medium

Netflix

7 views

Topics:

StacksRecursion

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-10⁶, 10⁶].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the nested lists contain `null` or empty lists?
What is the maximum depth of nesting allowed in the `nestedList`?
Can the integers within the nested lists be negative, zero, or have any specific range of values?
If `hasNext()` is called when the iterator is empty, should it return `false` or throw an exception?
Is the input `nestedList` mutable? Should the iterator preserve the original list's structure if modified after the iterator is created?

Brute Force Solution

Approach

The goal is to take a complicated structure of lists within lists and turn it into a simple, single list. The brute force method tackles this by completely unraveling the whole nested structure at the beginning. This means visiting every single element and extracting the integers one by one.

Here's how the algorithm would work step-by-step:

First, look at the very first item in the structure.
If it's a single number, put it directly into a temporary, simple list.
If it's a list itself, open that list and repeat the process for each item inside it.
Keep doing this for every nested list you find, going deeper and deeper until you only find single numbers.
Once you've processed everything, the temporary list will contain all the numbers in the order they appeared in the original structure, but now in a simple, flat format.
This pre-prepared simple list can be used to easily provide the next number when asked.

Code Implementation

class NestedIterator:

    def __init__(self, nestedList):
        self.flattened_list = []
        self.flatten_list(nestedList)
        self.current_index = 0

    def flatten_list(self, nested_list):
        for item in nested_list:
            if isinstance(item, int):
                self.flattened_list.append(item)

            # If list, recursively unpack it
            elif isinstance(item, list):

                self.flatten_list(item)

    def next(self):

        # Return the next element in the flattened list.
        next_element = self.flattened_list[self.current_index]
        self.current_index += 1
        return next_element

    def hasNext(self):

        # Check if there are more elements to iterate through
        return self.current_index < len(self.flattened_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided solution's time complexity is O(n), where n is the total number of integers and nested lists within the input. The brute force approach visits each element (integer or nested list) in the structure exactly once during the flattening process. Therefore, the time taken is directly proportional to the number of elements, resulting in a linear time complexity.

Space Complexity

O(N) – The described brute force solution creates a temporary, simple list to store all the integers from the nested structure. In the worst-case scenario, the nested list contains N integers, where N is the total number of integers in the original structure. Therefore, the temporary list can grow up to size N. The space complexity is thus O(N).

Optimal Solution

Approach

The core idea is to use a helper structure that automatically takes care of drilling down into nested lists. We'll manage a to-do list of lists; when we need the next element, we check if our current list is empty. If it is, we grab the next list from our to-do list.

Here's how the algorithm would work step-by-step:

Start with a to-do list containing only the initial nested list.
When asked for the next element, check if we have a current list that we are actively working through.
If the current list is empty, grab the next list from the to-do list and make it our current list.
If that next list contains a simple value (not another list), return it.
If that next list contains another nested list, add that nested list to the front of the to-do list, so we can process it later.
Repeat the process of checking the current list and to-do list until we find a simple value to return, or until there are no more lists to process.

Code Implementation

class NestedIterator:
    def __init__(self, nested_list):
        self.list_of_lists = [nested_list]
        self.current_list = []

    def next(self):
        self.has_next()
        return self.current_list.pop(0)

    def has_next(self):
        # Keep drilling down until we find a non-list element or run out of lists
        while not self.current_list:
            if not self.list_of_lists:
                return False

            self.current_list = self.list_of_lists.pop(0)

            # Flatten until the first element is not a list
            while self.current_list:
                first_element = self.current_list[0]
                if isinstance(first_element, list):
                    # Add the nested list to the front for later processing
                    nested_list_to_add = self.current_list.pop(0)
                    self.list_of_lists.insert(0, nested_list_to_add)
                    self.current_list = []
                    break
                else:
                    return True

        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) amortized – The hasNext() method iterates through nested lists only as needed to find the next integer. In the worst case, flattening a deeply nested list might take O(n) time for a single call to hasNext(), where n is the total number of NestedIntegers. However, over the entire sequence of next() and hasNext() calls, each NestedInteger is visited and processed at most once. Therefore, the amortized time complexity of hasNext() (and next()) is O(1), since the total work across all calls is proportional to the number of NestedIntegers in the input, and this cost is spread out across all calls.

Space Complexity

O(D) – The auxiliary space is dominated by the 'to-do list' which stores lists that need to be flattened. In the worst-case scenario, where we have deeply nested lists, the to-do list could hold up to D nested lists, where D is the maximum depth of nesting within the input nested list structure. Therefore, the space complexity is O(D), representing the maximum depth of the nested lists.

Edge Cases

Case	How to Handle
Null nestedList input	Throw IllegalArgumentException or return false for hasNext() depending on preferred behavior to signal invalid input.
Empty nestedList input: []	hasNext() should return false and next() should throw NoSuchElementException (or return null if that is allowed).
nestedList contains only empty lists: [ [], [], [] ]	hasNext() should return false after exhausting all empty lists, and next() should throw NoSuchElementException.
Deeply nested lists: [ [ [ [ 1 ] ] ] ]	The implementation should handle arbitrary nesting depth without causing a stack overflow or excessive memory usage, potentially using an iterative approach.
Large nested lists containing only a single integer at the deepest level.	The implementation must iterate efficiently and not create unnecessary intermediate lists that exhaust memory.
Nested list with mixed integers and lists at the same level: [1, [2, 3], 4, [5]]	Ensure the correct order of integers is returned in the flattened list (1, 2, 3, 4, 5).
Nested list contains very large integers (near Integer.MAX_VALUE or Integer.MIN_VALUE)	Ensure the solution correctly handles these boundary values without overflow issues during arithmetic operations (if any are involved in the implementation).
next() is called after hasNext() returns false.	next() should throw a NoSuchElementException, signaling the end of the iteration.