Flatten 2D Vector

Medium

Google

3 views

Topics:

Arrays

You are given a 2D vector (a list of lists of integers). Implement an iterator to flatten it into a 1D vector. The iterator should support two operations:

next(): Returns the next element in the flattened vector.
hasNext(): Returns true if there are more elements to iterate, false otherwise.

Example:

Input:
2D vector = [
  [1, 2],
  [3],
  [4, 5, 6]
]

Iterator iterator = new Iterator(2D vector);

iterator.hasNext(); // returns true
iterator.next();    // returns 1
iterator.next();    // returns 2
iterator.hasNext(); // returns true
iterator.next();    // returns 3
iterator.hasNext(); // returns true
iterator.next();    // returns 4
iterator.hasNext(); // returns true
iterator.next();    // returns 5
iterator.hasNext(); // returns true
iterator.next();    // returns 6
iterator.hasNext(); // returns false

Constraints:

You should implement the iterator class with next() and hasNext() methods.
The next() method should only be called if hasNext() returns true.
The 2D vector can contain empty lists.

How would you implement this, considering optimal time and space complexity? What are the potential edge cases to consider?

Flatten 2D Vector

Medium

Google

3 views

Topics:

Arrays

You are given a 2D vector (a list of lists of integers). Implement an iterator to flatten it into a 1D vector. The iterator should support two operations:

next(): Returns the next element in the flattened vector.
hasNext(): Returns true if there are more elements to iterate, false otherwise.

Example:

Input:
2D vector = [
  [1, 2],
  [3],
  [4, 5, 6]
]

Iterator iterator = new Iterator(2D vector);

iterator.hasNext(); // returns true
iterator.next();    // returns 1
iterator.next();    // returns 2
iterator.hasNext(); // returns true
iterator.next();    // returns 3
iterator.hasNext(); // returns true
iterator.next();    // returns 4
iterator.hasNext(); // returns true
iterator.next();    // returns 5
iterator.hasNext(); // returns true
iterator.next();    // returns 6
iterator.hasNext(); // returns false

Constraints:

You should implement the iterator class with next() and hasNext() methods.
The next() method should only be called if hasNext() returns true.
The 2D vector can contain empty lists.

How would you implement this, considering optimal time and space complexity? What are the potential edge cases to consider?

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 input 2D vector contain empty rows, and if so, how should `next()` and `hasNext()` behave in those cases?
What is the expected data type of the integers within the 2D vector, and are there any constraints on their range (e.g., positive, negative, zero, maximum/minimum values)?
If `next()` is called when `hasNext()` would return `false`, what should happen? Should I throw an exception, return a specific value like null, or is this considered an invalid state?
What are the size constraints on the 2D vector, both in terms of the number of rows and the number of elements in each row?
Is the 2D vector guaranteed to be rectangular (i.e., all rows have the same number of columns), or can it be jagged?

Brute Force Solution

Approach

The brute force approach completely unpacks the nested structure into a single, long list. It precomputes and stores everything from the start to avoid doing any calculations later when asked for the next element.

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

First, we take everything from the original structure and combine it into one simple, single list.
Imagine emptying out all the little boxes and putting everything into one big box.
Then, whenever someone asks for the next item, we just grab the next thing from our big box.

Code Implementation

class Vector2D:

    def __init__(self, vector_of_vectors):
        # Flatten the 2D vector into a single list upon initialization.
        self.flattened_list = []
        for vector in vector_of_vectors:
            for element in vector:
                self.flattened_list.append(element)

        # Keep track of the current index in the flattened list.
        self.current_index = 0

    def next(self):
        # Return the next element in the flattened list and advance the index.
        next_element = self.flattened_list[self.current_index]
        self.current_index += 1
        return next_element

    def hasNext(self):
        # Check if there are more elements in the flattened list.
        return self.current_index < len(self.flattened_list)

Big(O) Analysis

Time Complexity

O(N) – The brute force approach flattens the 2D vector into a single list upfront. The time complexity is determined by the number of elements (N) that need to be copied from the original 2D vector into the new, flattened list. Thus, the algorithm iterates through all elements in the 2D vector once, performing a constant-time operation (copying) for each. Therefore, the overall time complexity is O(N), where N is the total number of integers across all nested vectors.

Space Complexity

O(N) – The brute force approach creates a single list containing all the elements from the 2D vector. Where N is the total number of elements in the 2D vector, the auxiliary space used to store this flattened list will grow linearly with N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

We want to create a way to go through a list of lists as if it were one single list. The trick is to keep track of where we are in both the outer list and the inner list, advancing as needed.

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

Keep track of which list you're currently looking at.
Keep track of your current position within that list.
When someone asks for the next item, first check if there are any items remaining in your current list.
If there are, give them the next item and move to the next position in the current list.
If there are no more items in the current list, move to the next list in the overall list of lists.
If you run out of lists, then there are no more items to give.

Code Implementation

class Vector2D:

    def __init__(self, vector_of_vectors):
        self.vector_of_vectors = vector_of_vectors
        self.outer_index = 0
        self.inner_index = 0

    def next(self):
        return self.vector_of_vectors[self.outer_index][self.inner_index]

    def hasNext(self):
        # Iterate to the next valid position
        while self.outer_index < len(self.vector_of_vectors):
            if self.inner_index < len(self.vector_of_vectors[self.outer_index]):
                return True
            # Move to the next vector if current is exhausted
            else:
                self.outer_index += 1
                self.inner_index = 0

        return False

Big(O) Analysis

Time Complexity

O(1) – The hasNext() and next() operations each involve checking the current position in the lists and potentially advancing to the next inner list. These operations do not depend on the total number of elements in the 2D vector. Therefore, the time complexity for both operations is constant, O(1).

Space Complexity

O(1) – The algorithm described in the plain English explanation focuses on iterating through the input list of lists using index variables to keep track of the current position in the outer list and the current position in the inner list. Since only two index variables are required, and their size is independent of the total number of elements (N) in the 2D vector, the auxiliary space used remains constant. No additional data structures, such as temporary lists or hash maps, are created to store intermediate results. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input vector is null or empty.	The constructor should handle the null or empty input by initializing iterators to the end, so hasNext returns false immediately.
Input vector contains empty inner vectors.	The hasNext method should advance the outer iterator past empty inner vectors before returning true, and next() should gracefully handle this.
Input vector contains only one inner vector, which is also empty.	hasNext should return false immediately because there are no elements.
Input vector with a very large number of inner vectors and elements, potentially exceeding memory limits for eager flattening.	The iterator approach handles this well as it only keeps track of current iterators and not a flattened copy.
Consecutive empty inner vectors.	The hasNext() method must correctly skip over multiple consecutive empty inner vectors.
Integer overflow if inner vectors contain very large integers.	The problem does not explicitly require dealing with integer overflow as it only asks for iteration, so we proceed assuming integer values are in range.
All inner vectors are of size 1	The iterator should be initialized properly and iterate through each of the single elements.
Maximum size of the input 2D vector based on system memory limits	The iterative nature of the solution allows handling large inputs, but excessive memory allocation may cause issues.