# 251. Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

``````[
[1,2],
[3],
[4,5,6]
]
``````

By calling  next  repeatedly until  hasNext  returns false, the order of elements returned by  next  should be: `[1,2,3,4,5,6]`.

Hint:

1. How many variables do you need to keep track?
2. Two variables is all you need. Try with `x` and `y`.
3. Beware of empty rows. It could be the first few rows.
4. To write correct code, think about the invariant to maintain. What is it?
5. The invariant is `x` and `y` must always point to a valid point in the 2d vector. Should you maintain your invariant  ahead of time  or  right when you need it?
6. Not sure? Think about how you would implement `hasNext()`. Which is more complex?
7. Common logic in two different places should be refactored into a common method.

As an added challenge, try to code it using only iterators in C++ or iterators in Java.

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
for (auto a : vec2d) {
v.insert(v.end(), a.begin(), a.end());
}
}
int next() {
return v[i++];
}
bool hasNext() {
return i < v.size();
}
private:
vector<int> v;
int i = 0;
};
``````

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d): data(vec2d), x(0), y(0) {}

int next() {
hasNext();
return data[x][y++];
}
bool hasNext() {
while (x < data.size() && y == data[x].size()) {
++x;
y = 0;
}
return x < data.size();
}
private:
vector<vector<int>> data;
int x, y;
};
``````

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d): x(vec2d.begin()), end(vec2d.end()) {}

int next() {
hasNext();
return (*x)[y++];
}
bool hasNext() {
while (x != end && y == (*x).size()) {
++x;
y = 0;
}
return x != end;
}
private:
vector<vector<int>>::iterator x, end;
int y = 0;
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/251

Binary Search Tree Iterator

Zigzag Iterator

Peeking Iterator

Flatten Nested List Iterator

https://leetcode.com/problems/flatten-2d-vector/