We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Flatten 2D Vector

Number: 251

Difficulty: Medium

Paid? Yes

Companies: Airbnb, X, Google, Zenefits

Problem Description

Design an iterator that flattens a 2D vector. Implement the operations next() to return the next element and hasNext() to check if there exists another element. The iterator should seamlessly handle empty inner vectors.

Key Insights

  • Use two pointers (or indices), one for the outer list (row) and one for the inner list (column).
  • Skip over empty inner vectors to always point to a valid element.
  • Update pointers after each call to next() to prepare for subsequent calls.
  • Ensuring hasNext() advances pointers prevents redundant checks in next().

Space and Time Complexity

Time Complexity: O(1) per operation in average case; occasionally the advance step may traverse empty subarrays. Space Complexity: O(1) extra space, apart from storing the input vector.

Solution

We maintain two indices: one for rows and one for columns. In the constructor, we initialize these indices and immediately advance to the first valid element using an auxiliary function. Both next() and hasNext() call this function to ensure that the indices always point to a valid element in the vector. The next() function returns the current element and then moves the column pointer forward. If the end of an inner vector is reached, the pointers are advanced to the next non-empty row. This method avoids pre-flattening the 2D vector and results in efficient use of space and time.

Code Solutions

# Python implementation for Vector2D iterator.

class Vector2D:
    def __init__(self, vec):
        # Store the 2D vector and initialize pointers.
        self.vec = vec
        self.row = 0
        self.col = 0
        self._advance()  # Ensure pointer starts at a valid element

    def _advance(self):
        # Skip empty rows to find the next valid element.
        while self.row < len(self.vec) and self.col >= len(self.vec[self.row]):
            self.row += 1
            self.col = 0

    def next(self):
        # Returns the current element and advances pointers.
        result = self.vec[self.row][self.col]
        self.col += 1
        self._advance()  # Move to the next valid element after retrieval.
        return result

    def hasNext(self):
        # Check if current pointers point to a valid element.
        return self.row < len(self.vec)
        
# Example usage:
# vector2D = Vector2D([[1,2],[3],[4]])
# print(vector2D.next())  # returns 1
← Back to All Questions