251 - Flatten 2D Vector

Difficulty: Medium | Pattern: Iterator Design | Company tags: Google, Amazon, Twitter

Problem Statement

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

Example:

Vector2D i = new Vector2D([[1,2],[3],[4]]);
i.next()    → 1
i.next()    → 2
i.next()    → 3
i.hasNext() → true
i.hasNext() → true
i.next()    → 4
i.hasNext() → false

Algorithm Flow

Solution: Row/Col Pointer — O(1) amortized

Key insight: Track the current row and column. hasNext() advances to the next non-empty row before checking. This handles empty inner vectors.

class Vector2D:
    def __init__(self, vec: list[list[int]]):
        self.vec = vec
        self.row = 0
        self.col = 0
    
    def _advance(self):
        while self.row < len(self.vec) and self.col >= len(self.vec[self.row]):
            self.row += 1
            self.col = 0
    
    def next(self) -> int:
        self._advance()
        val = self.vec[self.row][self.col]
        self.col += 1
        return val
    
    def hasNext(self) -> bool:
        self._advance()
        return self.row < len(self.vec)

Dry Run

vec = [[1,2],[3],[4]]

call	row	col	action	result
next()	0	0	advance: row=0,col=0 valid → return 1, col=1	1
next()	0	1	advance: row=0,col=1 valid → return 2, col=2	2
next()	0	2	advance: col=2 gte len[0]=2 → row=1,col=0 → return 3, col=1	3
hasNext()	1	1	advance: col=1 gte len[1]=1 → row=2,col=0 → row=2 lt 3 → true	true
next()	2	0	return 4, col=1	4
hasNext()	2	1	advance: col=1 gte len[2]=1 → row=3,col=0 → row=3=len → false	false

✓

Handling Empty Inner Vectors

_advance() skips empty rows by checking col >= len(self.vec[self.row]). This works even if an inner vector has length 0.

Complexity

• Time: O(1) amortized — each element visited once
• Space: O(1) extra

Key Terms

Term	Definition
Iterator design pattern	An interface (next()/hasNext()) that exposes elements one at a time without revealing the underlying structure.
Lazy advancement	Deferring the work of skipping empty rows until next() or hasNext() is actually called, rather than pre-flattening.
Amortized O(1)	Each element's row/col pointer advances at most once across the whole iteration, so total advancement work is bounded by the number of elements.
Two-pointer state	Using row and col indices together to track position within a nested (2D) structure.
Empty subsequence skipping	Handling inner lists of length 0 correctly by looping past them in _advance() instead of assuming every row has at least one element.

FAQ

1. Can this be solved without extra space? Yes — the row/col pointer approach uses only O(1) extra space (two integers), unlike a pre-flattening approach that would use O(total elements).
2. What if the input is empty? If vec is [] or contains only empty inner lists, hasNext() correctly returns False immediately since _advance() pushes row past len(vec).
3. How would this change if the vector were 3D or arbitrarily nested? Replace the row/col pointers with an explicit stack of iterators (one per nesting level), advancing/popping as inner iterators are exhausted — this generalizes to N-level nesting (see Flatten Nested List Iterator, LC 341).
4. What's the follow-up interviewers usually ask? How to support remove() in addition to next()/hasNext(), and how to generalize to arbitrarily nested lists.
5. Why call _advance() in both next() and hasNext()? Both need to know the true current valid position; calling it in next() alone would fail if hasNext() is called consecutively without an intervening next().

Quick Revision

• The problem asks you to design an iterator (next/hasNext) over a 2D list as if it were flat.
• Maintain two pointers: row (which inner list) and col (index within that inner list).
• _advance() skips forward past any exhausted or empty inner lists before reading/checking.
• Call _advance() at the start of both next() and hasNext() to keep state consistent.
• next() reads vec[row][col], then increments col.
• hasNext() just checks whether row is still within bounds after advancing.
• Handles empty inner vectors naturally since _advance() loops, not just checks once.
• Time: O(1) amortized per call; Space: O(1) extra (no flattening/copying).
• Alternative: eagerly flatten into a list/queue up front — simpler but O(n) space and doesn't scale to lazy/infinite iterators.

Related Problems

• Flatten Nested List Iterator (LC 341) — same iterator design pattern but for arbitrarily nested lists, solved with an explicit stack.
• Peeking Iterator (LC 284) — extends the iterator pattern with a peek() operation requiring cached lookahead state.
• Zigzag Iterator (LC 281) — another custom iterator problem requiring careful pointer/state management across multiple lists.