NUHMAN.com

Introduction

LeetCode 251: Flatten 2D Vector is a design-focused problem that tests your object-oriented programming (OOP) skills, particularly around implementing custom iterators.

Given a 2D vector, we need to flatten it and support the typical iterator operations: next() and hasNext().

Let’s walk through how to solve it in Python step by step.

Problem Statement

Implement an iterator to flatten a 2D vector. It should support the next() and hasNext() operations.

Your implementation should be able to handle empty rows and skip them.

Example:

python

vec2d = [[1,2], [3], [], [4,5,6]]
i = Vector2D(vec2d)
while i.hasNext(): 
    print(i.next())

Output:

1
2
3
4
5
6

Step-by-Step Solution in Python

Step 1: Understand the Requirements

We must create a class Vector2D with two methods:

• next() – returns the next element
• hasNext() – returns whether more elements are available

We also need to handle:

• Empty inner lists ([])
• Iteration that skips directly to the next valid number

Step 2: Class Design

To maintain position, we track:

• row → index of outer list
• col → index of inner list

Each time we call next(), we return the current value and move forward. Before each call, we ensure we’re not pointing at an empty sublist using a helper function.

Step 3: Code It

python

class Vector2D:
    def __init__(self, vec: list[list[int]]):
        self.vec = vec
        self.row = 0
        self.col = 0
        self._advance()

    def _advance(self):
        # Skip empty sublists or end of current sublist
        while self.row < len(self.vec) and self.col >= len(self.vec[self.row]):
            self.row += 1
            self.col = 0

    def next(self) -> int:
        if not self.hasNext():
            raise StopIteration

        val = self.vec[self.row][self.col]
        self.col += 1
        self._advance()
        return val

    def hasNext(self) -> bool:
        self._advance()
        return self.row < len(self.vec)

Explanation of the Code

1. __init__
2. Initializes row and col to the start of the 2D list and calls _advance() to skip empty rows.
3. _advance
4. A helper that moves the pointers forward until they land on a valid element.
5. next()
6. Returns the current element and moves the pointer to the next element.
7. hasNext()
8. Calls _advance() to skip empties and checks if there’s a valid value left.

Key Edge Cases Handled

• Empty rows like [[], [1, 2]]
• Completely empty matrix like []
• Rows that end midway and need a jump to the next one

Time and Space Complexity

• Time Complexity:
• next() and hasNext() are both amortized O(1) due to pointer advancement.
• Space Complexity:
• O(1) – No extra space is used beyond pointers.

Conclusion

LeetCode 251 is a great example of a design problem where understanding iterator mechanics and edge case handling is crucial. It teaches:

• Class structure
• Clean method separation (_advance)
• Efficient iteration without pre-flattening the structure