Problem Description

You need to design an iterator that can traverse through a 2D vector (a list of lists) as if it were a 1D vector. The iterator should flatten the 2D structure and allow sequential access to all elements.

The Vector2D class needs to implement three methods:

1. Constructor Vector2D(int[][] vec): Takes a 2D vector as input and initializes the iterator. The 2D vector may contain empty lists.

2. next(): Returns the next integer element in the flattened sequence and advances the internal pointer to the subsequent element. The problem guarantees that next() will only be called when there are remaining elements.

3. hasNext(): Returns true if there are more elements to iterate through, false otherwise.

The key challenge is handling the 2D structure efficiently. The solution uses two pointers:

• i: tracks the current row (outer list index)
• j: tracks the current column (inner list index within row i)

The forward() helper method is crucial - it skips over any empty lists and positions the pointers at the next valid element. When j reaches or exceeds the length of the current row, it moves to the next row and resets j to 0.

For example, given vec = [[1,2],[3],[],[4,5,6]]:

• Calling next() repeatedly would return: 1, 2, 3, 4, 5, 6
• The iterator automatically skips the empty list at index 2
• hasNext() returns true until all elements are consumed

The algorithm ensures O(1) average time complexity for both next() and hasNext() operations by maintaining the current position with the two pointers and advancing them as needed.

Intuition

When we need to iterate through a 2D structure as if it were 1D, the natural approach is to think about how we manually traverse such a structure. If we were reading a book with multiple chapters (rows) and each chapter has multiple pages (elements), we'd read page by page within a chapter, then move to the next chapter when done.

This translates directly to using two pointers: one for which "chapter" (row) we're in, and another for which "page" (column) within that chapter. We start at position [0, 0] - the first element of the first list.

The trickiest part is handling empty lists. In our book analogy, some chapters might have no pages. We can't stop at an empty chapter - we need to skip ahead to find the next chapter with content. This is why we need a mechanism to "fast-forward" through empty sections.

The key insight is to separate the navigation logic from the retrieval logic. Before trying to access any element (in both next() and hasNext()), we first ensure our pointers are positioned at a valid location. This is achieved through the forward() method, which advances the pointers past any empty lists or completed rows.

Why check j >= len(self.vec[self.i]) in the forward method? When we finish reading all elements in a row (after calling next() on the last element), our column pointer j moves beyond the current row's boundary. This signals that we need to move to the next row and reset j to 0.

This design elegantly handles all edge cases:

• Multiple consecutive empty lists are skipped automatically
• The transition between rows happens seamlessly
• We don't need to flatten the entire 2D vector upfront (which would use extra space)

The solution is essentially simulating how we'd naturally iterate through a 2D structure, with smart pointer management to handle the boundaries and empty spaces.

Solution Approach

The implementation uses a two-pointer approach with a helper method to manage navigation through the 2D vector.

Data Structure:

• Store the original 2D vector vec without flattening (space-efficient)
• Maintain two integer pointers: i for the current row index and j for the current column index within row i

Core Algorithm - The forward() Method:

The heart of the solution is the forward() helper method that ensures our pointers always point to a valid element or have moved past all elements:

def forward(self):
    while self.i < len(self.vec) and self.j >= len(self.vec[self.i]):
        self.i += 1
        self.j = 0

This method:

1. Checks if we're still within bounds (i < len(self.vec))
2. If the current column index j has reached or exceeded the current row's length, it means:
   • Either we've consumed all elements in the current row
   • Or the current row is empty (length 0)
3. Moves to the next row (i += 1) and resets the column pointer (j = 0)
4. Continues this process until finding a row with available elements or reaching the end

Implementation of next():

def next(self) -> int:
    self.forward()  # Ensure pointers are at a valid position
    ans = self.vec[self.i][self.j]  # Get current element
    self.j += 1  # Move column pointer forward
    return ans

Steps:

1. Call forward() to skip any empty rows and position at the next valid element
2. Retrieve the element at current position [i, j]
3. Increment j to prepare for the next call
4. Return the retrieved element

Implementation of hasNext():

def hasNext(self) -> bool:
    self.forward()  # Skip to next valid position if needed
    return self.i < len(self.vec)  # Check if still within bounds

Steps:

1. Call forward() to ensure we're either at a valid element or past all elements
2. Return true if i is still within the vector bounds, false otherwise

Why This Works:

The pattern ensures that before any element access or existence check, the pointers are properly positioned. After calling forward():

• If elements remain: i points to a valid row and j < len(self.vec[self.i])
• If no elements remain: i >= len(self.vec)

This lazy evaluation approach means we only advance through the structure as needed, making the solution both time and space efficient. The average time complexity is O(1) for both operations, though in worst case (many empty lists), forward() might need to skip multiple rows.

Example Walkthrough

Let's walk through the solution with vec = [[1,2],[],[3]]:

Initial State:

• vec = [[1,2],[],[3]]
• i = 0, j = 0 (pointing to first element of first list)

Operation 1: hasNext()

1. Call forward(): Check if j >= len(vec[0]) → 0 >= 2? No, so no changes needed
2. Check i < len(vec) → 0 < 3? Yes
3. Return true

Operation 2: next()

1. Call forward(): j = 0 < 2, pointers stay at [0,0]
2. Get element: vec[0][0] = 1
3. Increment j: Now i = 0, j = 1
4. Return 1

Operation 3: next()

1. Call forward(): j = 1 < 2, pointers stay at [0,1]
2. Get element: vec[0][1] = 2
3. Increment j: Now i = 0, j = 2
4. Return 2

Operation 4: hasNext()

1. Call forward():
   • Check: j >= len(vec[0]) → 2 >= 2? Yes!
   • Move to next row: i = 1, j = 0
   • Check again: j >= len(vec[1]) → 0 >= 0? Yes! (empty list)
   • Move to next row: i = 2, j = 0
   • Check again: j >= len(vec[2]) → 0 >= 1? No, stop
2. Check i < len(vec) → 2 < 3? Yes
3. Return true

Operation 5: next()

1. Call forward(): Already at valid position [2,0] from previous hasNext()
2. Get element: vec[2][0] = 3
3. Increment j: Now i = 2, j = 1
4. Return 3

Operation 6: hasNext()

1. Call forward():
   • Check: j >= len(vec[2]) → 1 >= 1? Yes!
   • Move to next row: i = 3, j = 0
   • Check: i < len(vec) → 3 < 3? No, we're past the end
2. Check i < len(vec) → 3 < 3? No
3. Return false

The key insight: forward() automatically skips the empty list at index 1, ensuring we always land on a valid element or move past all elements entirely.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(1) - Simply initializes three variables without any loops or operations dependent on input size.
• next(): O(k) where k is the number of empty rows that need to be skipped. In the worst case where all rows except the last are empty, this becomes O(m) where m is the number of rows. Amortized over all calls, each element is accessed exactly once, giving amortized O(1).
• hasNext(): O(k) where k is the number of empty rows that need to be skipped from the current position. Worst case is O(m) where m is the number of rows. Amortized O(1).
• forward(): O(k) where k is the number of empty rows to skip. This helper method iterates through empty rows until finding a non-empty row or reaching the end.

Space Complexity:

• O(1) - The class only stores references to the input vector and two integer pointers (i and j). No additional space is used that scales with the input size. The input vector itself is not counted as it's passed by reference and not created by this class.

Overall Analysis:

• For n total elements across all rows and m rows:
  • Amortized time per operation: O(1)
  • Worst-case time per operation: O(m)
  • Total time for iterating through all elements: O(n + m)
  • Space complexity: O(1) auxiliary space

Common Pitfalls

1. Not Handling Empty Rows Properly

The Pitfall: A common mistake is forgetting to skip empty rows or only checking for them in one method. Developers often write code like:

def next(self) -> int:
    result = self.vec[self.row][self.col]  # Direct access without checking
    self.col += 1
    if self.col >= len(self.vec[self.row]):
        self.row += 1
        self.col = 0
    return result

This fails when encountering empty rows because self.vec[self.row] might be an empty list, causing an index out of bounds error.

The Solution: Always call the _advance_to_next() helper method before accessing elements. This ensures the pointers skip over any empty rows:

def next(self) -> int:
    self._advance_to_next()  # Skip empty rows first
    result = self.vec[self.row][self.col]
    self.col += 1
    return result

2. Incorrect Pointer Management After next()

The Pitfall: Incrementing both pointers or forgetting to increment at all:

def next(self) -> int:
    self._advance_to_next()
    result = self.vec[self.row][self.col]
    # Wrong: incrementing row instead of column
    self.row += 1  
    return result

# Or forgetting to increment at all:
def next(self) -> int:
    self._advance_to_next()
    return self.vec[self.row][self.col]  # Pointers not moved

The Solution: Only increment the column pointer after retrieving the element. The row advancement is handled by _advance_to_next() in the next call:

def next(self) -> int:
    self._advance_to_next()
    result = self.vec[self.row][self.col]
    self.col += 1  # Only increment column
    return result

3. Eager Evaluation Instead of Lazy Evaluation

The Pitfall: Flattening the entire 2D vector in the constructor:

def __init__(self, vec: List[List[int]]):
    self.flattened = []
    for row in vec:
        self.flattened.extend(row)
    self.index = 0

While this works, it uses O(n) extra space where n is the total number of elements, defeating the purpose of an iterator pattern.

The Solution: Keep the original 2D structure and navigate through it with pointers. This maintains O(1) space complexity (excluding the input):

def __init__(self, vec: List[List[int]]):
    self.row = 0
    self.col = 0
    self.vec = vec  # Keep original structure

4. Inefficient _advance_to_next() Implementation

The Pitfall: Using recursive calls or checking conditions inefficiently:

def _advance_to_next(self) -> None:
    # Inefficient: checking same condition multiple times
    if self.row < len(self.vec):
        if self.col >= len(self.vec[self.row]):
            self.row += 1
            self.col = 0
            self._advance_to_next()  # Recursive call

Recursive calls can lead to stack overflow with many consecutive empty rows.

The Solution: Use a while loop that handles all empty rows in one pass:

def _advance_to_next(self) -> None:
    while self.row < len(self.vec) and self.col >= len(self.vec[self.row]):
        self.row += 1
        self.col = 0

5. Not Calling _advance_to_next() in Both Methods

The Pitfall: Only calling the helper in next() but not in hasNext():

def hasNext(self) -> bool:
    # Wrong: directly checking without skipping empty rows
    return self.row < len(self.vec)

This incorrectly returns True even when only empty rows remain.

The Solution: Both methods must call _advance_to_next() to ensure accurate state:

def hasNext(self) -> bool:
    self._advance_to_next()  # Essential for correctness
    return self.row < len(self.vec)