Flatten 2D Vector solution and explanation
9 more videos on this problem
LeetCode Q 251: Flatten 2D VectorSweet AI · 11:30 · 1K views
Leetcode 251 Flatten 2D Vector(Java版)(所有题目完整视频及代码添加小助手+VX: flageek996,网址:www.flageek996.com)FLAGeek官方频道 · 6:20 · 817 views
251. Flatten 2D VectorMuerde un zombie · 4:58 · 684 views
Leetcode 251 Flatten 2D Vector pythonFLAGeek官方频道 · 7:01 · 627 views
251. Flatten 2D Vector (Leetcode Medium)Programming Live with Larry · 7:21 · 505 views
LeetCode 251 Flatten 2D Vector | OO DesignHow we live in Texas · 4:09 · 378 views
Leetcode 251 Flatten 2D Vector C++FLAGeek官方频道 · 5:56 · 323 views
Flatten 2D Vector (Medium), C++, LeetcodeH William Polenz · 1:00:46 · 312 views
Leetcode 251. Flatten 2D Vector (iterator)LetsCode · 2:09 · 196 views
Flatten 2D VectorOwen Wu · 2:16 · 81 views
The problem
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.
Solution
class Vector2D:
def __init__(self, vec: List[List[int]]):
self.i = 0
self.j = 0
self.vec = vec
def next(self) -> int:
self.forward()
ans = self.vec[self.i][self.j]
self.j += 1
return ans
def hasNext(self) -> bool:
self.forward()
return self.i < len(self.vec)
def forward(self):
while self.i < len(self.vec) and self.j >= len(self.vec[self.i]):
self.i += 1
self.j = 0
# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()class Vector2D {
private int i;
private int j;
private int[][] vec;
public Vector2D(int[][] vec) {
this.vec = vec;
}
public int next() {
forward();
return vec[i][j++];
}
public boolean hasNext() {
forward();
return i < vec.length;
}
private void forward() {
while (i < vec.length && j >= vec[i].length) {
++i;
j = 0;
}
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D obj = new Vector2D(vec);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/class Vector2D {
public:
Vector2D(vector<vector<int>>& vec) {
this->vec = move(vec);
}
int next() {
forward();
return vec[i][j++];
}
bool hasNext() {
forward();
return i < vec.size();
}
private:
int i = 0;
int j = 0;
vector<vector<int>> vec;
void forward() {
while (i < vec.size() && j >= vec[i].size()) {
++i;
j = 0;
}
}
};
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D* obj = new Vector2D(vec);
* int param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/class Vector2D {
i: number;
j: number;
vec: number[][];
constructor(vec: number[][]) {
this.i = 0;
this.j = 0;
this.vec = vec;
}
next(): number {
this.forward();
return this.vec[this.i][this.j++];
}
hasNext(): boolean {
this.forward();
return this.i < this.vec.length;
}
forward(): void {
while (this.i < this.vec.length && this.j >= this.vec[this.i].length) {
++this.i;
this.j = 0;
}
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* var obj = new Vector2D(vec)
* var param_1 = obj.next()
* var param_2 = obj.hasNext()
*/type Vector2D struct {
i, j int
vec [][]int
}
func Constructor(vec [][]int) Vector2D {
return Vector2D{vec: vec}
}
func (this *Vector2D) Next() int {
this.forward()
ans := this.vec[this.i][this.j]
this.j++
return ans
}
func (this *Vector2D) HasNext() bool {
this.forward()
return this.i < len(this.vec)
}
func (this *Vector2D) forward() {
for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) {
this.i++
this.j = 0
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* obj := Constructor(vec);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/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 |
Frequently asked questions
Is Flatten 2D Vector easy or hard?
Flatten 2D Vector is generally rated Medium difficulty. The logic of flattening is straightforward, but designing a clean iterator that skips empty rows and maintains correct state between next() and hasNext() requires careful handling.
Flatten 2D Vector Python/Java solution
In Python and Java, the typical implementation stores two pointers for row and column. The hasNext() method skips empty rows and checks bounds, while next() returns the current element and advances the column pointer. This approach keeps the solution O(n) time and O(1) extra space.
How to solve Flatten 2D Vector in O(n)?
Track two pointers: row index and column index. In hasNext(), advance the row pointer while the current row is empty or fully consumed. The next() method simply returns vec[row][col] and increments the column pointer. Since every element is accessed once, the overall complexity is O(n).
What is the best approach for Flatten 2D Vector?
The two‑pointer iterator approach is considered the best solution. Maintain two indices: one for the row and one for the column. The iterator advances rows when the current inner vector is exhausted and returns elements sequentially. This processes each element once with O(n) time and O(1) extra space.
Is Flatten 2D Vector asked at Google/Amazon/Meta?
Flatten 2D Vector is a common iterator design problem that appears in interviews at companies like Google, Amazon, and Meta. It tests understanding of lazy iteration, handling nested arrays, and designing clean next()/hasNext() APIs.
What data structure is used in Flatten 2D Vector?
The problem primarily uses arrays (or lists) combined with an iterator design pattern. The optimal solution maintains two indices to traverse the nested array structure. Some alternative implementations also use queues or pre-flattened arrays.
What is the time complexity of Flatten 2D Vector?
The optimal iterator design runs in O(n) total time where n is the total number of elements in the 2D vector. Each element is visited exactly once during iteration. The space complexity can be O(1) if you only store row and column pointers.
