Flatten 2D Vector - Video Solutions
LeetCode Q 251: Flatten 2D Vector
Flatten 2D Vector - Video Solution
Watch 10 video solutions for Flatten 2D Vector, a medium level problem involving Array, Two Pointers, Design. This walkthrough by Sweet AI has 1,442 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.
Implement the Vector2D class:
Vector2D(int[][] vec)initializes the object with the 2D vectorvec.next()returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls tonextare valid.hasNext()returnstrueif there are still some elements in the vector, andfalseotherwise.
Example 1:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False
Constraints:
0 <= vec.length <= 2000 <= vec[i].length <= 500-500 <= vec[i][j] <= 500- At most
105calls will be made tonextandhasNext.
Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pre‑Flatten Array | O(n) | O(n) | When simplicity matters and memory overhead is acceptable |
| Two Pointer Iterator | O(n) | O(1) | Best general solution; avoids copying data and works directly on the input |
| Queue Based Iterator | O(n) | O(n) | When iteration speed after initialization is the priority |