Watch 10 video solutions for Flatten 2D Vector, a medium level problem involving Array, Two Pointers, Design. This walkthrough by Greg Hogg has 649,117 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Overview: Design an iterator that flattens a 2D vector so elements are returned sequentially through next() and hasNext(). The iterator should move through each inner list and skip empty rows while maintaining the correct order.
Approach 1: Pre-Flatten the Vector (O(n) time, O(n) space)
The most straightforward approach is to flatten the entire 2D vector during initialization. Iterate through every row of the matrix and push each element into a single 1D array. The iterator then simply tracks a pointer over this flattened list. Both next() and hasNext() become trivial constant-time operations. The downside is memory usage since all values are copied into another array. This approach works well when memory is not a concern and implementation simplicity matters.
Approach 2: Two Pointers with Lazy Traversal (O(n) time, O(1) space)
The optimal solution avoids flattening the entire structure. Maintain two indices: row and col. The row pointer tracks which inner list you're in, while col tracks the element within that list. When hasNext() is called, advance the row pointer while the current row is exhausted or empty. Once a valid element exists, next() returns vector[row][col] and increments the column pointer. Each element is visited exactly once, giving O(n) total time and O(1) extra space. This pattern is common in iterator design problems and is frequently implemented using two pointers.
Approach 3: Iterator-Based Row Traversal (O(n) time, O(1) space)
Languages with strong iterator support can store iterators for the current row and end positions. When the current iterator reaches the end of a row, move to the next row and reset the iterator. This avoids manual index handling and produces cleaner code in languages like C++ or Java. Conceptually it's the same as the two-pointer method, but relies on iterator objects instead of numeric indices. The algorithm still processes each element once.
Conceptually, this problem combines array traversal with design of an efficient iterator. The key challenge is correctly skipping empty rows while keeping operations constant time.
Recommended for interviews: The lazy traversal solution using two pointers is the expected answer. It avoids unnecessary memory allocation and demonstrates understanding of iterator design. Starting with the pre-flatten approach shows baseline reasoning, then optimizing to O(1) space highlights strong problem-solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pre-Flatten 2D Vector | O(n) | O(n) | When implementation simplicity matters and extra memory is acceptable |
| Two Pointers Lazy Traversal | O(n) | O(1) | Best general solution; avoids copying data and processes elements on demand |
| Row Iterator Traversal | O(n) | O(1) | Useful in languages with strong iterator APIs like C++ or Java |
