Flatten 2D Vector - Solution & Explanation

Problem Overview: You need to design an iterator over a 2D list of integers so that elements are returned one by one in row‑major order. The iterator must support next() and hasNext() while correctly skipping empty inner lists.

Approach 1: Pre‑Flatten the Vector (O(n) time, O(n) space)

The simplest strategy is to flatten the entire 2D vector during initialization. Iterate through every row and append its elements into a single 1D array. Maintain a pointer idx that moves forward each time next() is called, while hasNext() checks whether idx < flattened.size(). This makes iteration trivial because the structure behaves like a normal array iterator. The tradeoff is memory usage: storing a full copy of all elements requires O(n) extra space.

Approach 2: Two Pointers Across Rows (O(n) time, O(1) space)

A more efficient design uses two indices: row for the outer vector and col for the current position inside that row. When hasNext() runs, advance row until a row with remaining elements is found, resetting col to zero each time a row is exhausted. Once a valid row exists, next() returns vec[row][col] and increments col. Each element is visited exactly once, giving O(n) total time while using only constant extra space. This pattern resembles an iterator design commonly seen with nested arrays and is closely related to two pointers and design interview questions.

Approach 3: Queue‑Based Iterator (O(n) time, O(n) space)

Another implementation pushes all elements into a queue during construction. Each next() pops from the front, and hasNext() checks whether the queue is empty. This works well when the interface is consumed heavily after initialization, since every operation becomes constant time. However, it duplicates the data structure in memory, leading to O(n) space overhead and unnecessary preprocessing compared to the pointer approach.

Recommended for interviews: The two‑pointer iterator is the expected solution. It avoids copying the data and demonstrates that you can design a lazy iterator that walks through nested containers. Showing the pre‑flatten idea first proves correctness quickly, but the constant‑space iterator shows stronger understanding of array traversal and iterator design patterns.