Flatten 2D Vector

Flatten 2D Vector

1. What is this problem about?

The Flatten 2D Vector interview question asks you to implement an iterator for a list of lists. You are given a 2D array (e.g., [[1, 2], [], [3]]) and need to provide next() and hasNext() methods that allow a user to traverse all the elements as if they were in a single flat 1D list.

2. Why is this asked in interviews?

Companies like Airbnb and Google ask the Flatten 2D Vector coding problem to test a candidate's mastery of the Iterator interview pattern. It evaluations your ability to manage multiple pointers (one for the outer list and one for the inner list) and handle "empty" sub-lists correctly without crashing or skipping elements.

3. Algorithmic pattern used

This is a Two-Pointer Simulation problem.

1. Pointers:
   • row: Index of the current sub-list.
   • col: Index of the element within the current sub-list.
2. hasNext() (The Core): This method should do the heavy lifting. If the current col is at the end of the current row, increment row and reset col until you find a non-empty sub-list or reach the end of the 2D array.
3. next(): Simply call hasNext() to ensure you are at a valid element, then return vec[row][col++].

4. Example explanation

Input: [[1, 2], [], [3]]

1. Initial: row=0, col=0.
2. next(): Returns vec[0][0] (1). col=1.
3. next(): Returns vec[0][1] (2). col=2.
4. next():
   • hasNext() sees col=2 is end of vec[0].
   • Moves to row=1. vec[1] is empty.
   • Moves to row=2. col reset to 0.
   • Returns vec[2][0] (3).

5. Common mistakes candidates make

• Lazy Pointer Update: Waiting until next() is called to find the next valid element. It’s much cleaner to handle the skipping of empty lists inside hasNext().
• Memory Overhead: Converting the 2D vector into a 1D list in the constructor. While easy, it uses $O(N)$ extra space, which is often forbidden in iterator design questions.
• OutOfBounds: Failing to check if row has exceeded the 2D array size before checking for empty lists.

6. Interview preparation tip

Always implement iterators Lazily. The goal is to provide elements one-by-one without pre-processing the entire dataset. This is a foundational Design interview pattern for large-scale data systems.