LeetCode 251: Flatten 2D Vector (Row/Col Pointer Iterator)
LeetCode 251DesignIteratorToday we solve LeetCode 251 - Flatten 2D Vector.
Source: https://leetcode.com/problems/flatten-2d-vector/
English
Problem Summary
Design an iterator over a 2D integer vector. Implement next() to return the next element and hasNext() to tell whether elements remain.
Key Idea
Maintain two pointers: r for row, c for column. Before reading, advance r while current row is exhausted (or empty), and reset c = 0 when moving to the next row.
Algorithm
1) Keep vec, r, c.
2) Helper advance(): while r < rows and c >= vec[r].length, do r++, c=0.
3) hasNext() calls advance() then checks r < rows.
4) next() calls hasNext(), returns vec[r][c++].
Complexity
Amortized O(1) per operation, because each row and element is skipped or visited at most once. Space complexity O(1) extra.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Vector2D {
private final int[][] vec;
private int r = 0, c = 0;
public Vector2D(int[][] vec) {
this.vec = vec;
}
private void advance() {
while (r < vec.length && c >= vec[r].length) {
r++;
c = 0;
}
}
public int next() {
if (!hasNext()) throw new RuntimeException("No more elements");
return vec[r][c++];
}
public boolean hasNext() {
advance();
return r < vec.length;
}
}type Vector2D struct {
vec [][]int
r, c int
}
func Constructor(vec [][]int) Vector2D {
return Vector2D{vec: vec}
}
func (it *Vector2D) advance() {
for it.r < len(it.vec) && it.c >= len(it.vec[it.r]) {
it.r++
it.c = 0
}
}
func (it *Vector2D) Next() int {
if !it.HasNext() {
panic("No more elements")
}
v := it.vec[it.r][it.c]
it.c++
return v
}
func (it *Vector2D) HasNext() bool {
it.advance()
return it.r < len(it.vec)
}class Vector2D {
private:
vector<vector<int>> vec;
int r = 0, c = 0;
void advance() {
while (r < (int)vec.size() && c >= (int)vec[r].size()) {
r++;
c = 0;
}
}
public:
Vector2D(vector<vector<int>>& v) : vec(v) {}
int next() {
if (!hasNext()) throw runtime_error("No more elements");
return vec[r][c++];
}
bool hasNext() {
advance();
return r < (int)vec.size();
}
};class Vector2D:
def __init__(self, vec):
self.vec = vec
self.r = 0
self.c = 0
def _advance(self):
while self.r < len(self.vec) and self.c >= len(self.vec[self.r]):
self.r += 1
self.c = 0
def next(self) -> int:
if not self.hasNext():
raise Exception("No more elements")
val = self.vec[self.r][self.c]
self.c += 1
return val
def hasNext(self) -> bool:
self._advance()
return self.r < len(self.vec)var Vector2D = function(vec) {
this.vec = vec;
this.r = 0;
this.c = 0;
};
Vector2D.prototype.advance = function() {
while (this.r < this.vec.length && this.c >= this.vec[this.r].length) {
this.r++;
this.c = 0;
}
};
Vector2D.prototype.hasNext = function() {
this.advance();
return this.r < this.vec.length;
};
Vector2D.prototype.next = function() {
if (!this.hasNext()) throw new Error("No more elements");
return this.vec[this.r][this.c++];
};中文
题目概述
实现一个二维整数数组的迭代器，支持 next() 返回下一个元素，hasNext() 判断是否还有元素。
核心思路
用两个指针：r 表示行，c 表示列。每次访问前先清理空位，如果当前行已读完就移动到下一行并把列重置为 0，因此可以自动跳过空行。
算法步骤
1）维护 vec、r、c。
2）实现 advance()：当 r 未越界且 c 已到当前行末尾时，执行 r++、c=0。
3）hasNext() 先调用 advance()，再判断 r < rows。
4）next() 先确保有元素，再返回 vec[r][c++]。
复杂度分析
均摊时间复杂度 O(1)，因为每个元素只访问一次、每一行最多跳过一次。额外空间复杂度 O(1)。
参考实现（Java / Go / C++ / Python / JavaScript）
class Vector2D {
private final int[][] vec;
private int r = 0, c = 0;
public Vector2D(int[][] vec) {
this.vec = vec;
}
private void advance() {
while (r < vec.length && c >= vec[r].length) {
r++;
c = 0;
}
}
public int next() {
if (!hasNext()) throw new RuntimeException("No more elements");
return vec[r][c++];
}
public boolean hasNext() {
advance();
return r < vec.length;
}
}type Vector2D struct {
vec [][]int
r, c int
}
func Constructor(vec [][]int) Vector2D {
return Vector2D{vec: vec}
}
func (it *Vector2D) advance() {
for it.r < len(it.vec) && it.c >= len(it.vec[it.r]) {
it.r++
it.c = 0
}
}
func (it *Vector2D) Next() int {
if !it.HasNext() {
panic("No more elements")
}
v := it.vec[it.r][it.c]
it.c++
return v
}
func (it *Vector2D) HasNext() bool {
it.advance()
return it.r < len(it.vec)
}class Vector2D {
private:
vector<vector<int>> vec;
int r = 0, c = 0;
void advance() {
while (r < (int)vec.size() && c >= (int)vec[r].size()) {
r++;
c = 0;
}
}
public:
Vector2D(vector<vector<int>>& v) : vec(v) {}
int next() {
if (!hasNext()) throw runtime_error("No more elements");
return vec[r][c++];
}
bool hasNext() {
advance();
return r < (int)vec.size();
}
};class Vector2D:
def __init__(self, vec):
self.vec = vec
self.r = 0
self.c = 0
def _advance(self):
while self.r < len(self.vec) and self.c >= len(self.vec[self.r]):
self.r += 1
self.c = 0
def next(self) -> int:
if not self.hasNext():
raise Exception("No more elements")
val = self.vec[self.r][self.c]
self.c += 1
return val
def hasNext(self) -> bool:
self._advance()
return self.r < len(self.vec)var Vector2D = function(vec) {
this.vec = vec;
this.r = 0;
this.c = 0;
};
Vector2D.prototype.advance = function() {
while (this.r < this.vec.length && this.c >= this.vec[this.r].length) {
this.r++;
this.c = 0;
}
};
Vector2D.prototype.hasNext = function() {
this.advance();
return this.r < this.vec.length;
};
Vector2D.prototype.next = function() {
if (!this.hasNext()) throw new Error("No more elements");
return this.vec[this.r][this.c++];
};
Comments