# 20ms C++ Solution with Explanations

• The idea is very simple. We keep two variables `row` and `col` for the range of rows and cols. Specifically, `row` is the number of rows of `vec2d` and `col` is the number of columns of the current 1d vector in `vec2d`. We also keep two variables `r` and `c` to point to the current element.

In the constructor, we initialize `row` and `col` as above and initialize both `r` and `c` to be `0` (pointing to the first element).

In `hasNext()`, we just need to check whether `r` and `c` are still in the range limited by `row` and `col`.

In `next()`, we first record the current element, which is returned later. Then we update the running indexes and possibly the range if the current element is the last element of the current 1d vector.

A final and important note, since in `next()`, we record the current element, we need to guarantee that there is an element. So we implement a helper function `skipEmptyVector()` to skip the empty vectors. It is also important to handle the case that `vec2d` is empty (in this case, we set `col = -1`).

The time complexity of `hasNext()` is obviously `O(1)` and the time complexity of `next` is also `O(1)` in an amortized sense.

The code is as follows.

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
data = vec2d;
r = c = 0;
row = vec2d.size();
col = (row == 0 ? -1 : data[r].size());
skipEmptyVector();
}

int next() {
int elem = data[r][c];
if (c == col - 1) {
r++;
c = 0;
col = data[r].size();
}
else c++;
skipEmptyVector();
return elem;
}

bool hasNext() {
return col != -1 && (r < row && c < col);
}
private:
vector<vector<int>> data;
int row, col, r, c;
void skipEmptyVector(void) {
while (!col) {
r++;
col = data[r].size();
}
}
};

/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i(vec2d);
* while (i.hasNext()) cout << i.next();
*/
``````

Updates: Since we need to copy the `vec2d`, we can just copy it into a 1d `vector<int>`.

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
int row = vec2d.size();
for (int r = 0; r < row; r++) {
int col = vec2d[r].size();
for (int c = 0; c < col; c++)
data.push_back(vec2d[r][c]);
}
idx = 0;
}

int next() {
return data[idx++];
}

bool hasNext() {
return idx < data.size();
}
private:
vector<int> data;
int idx;
};

/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i(vec2d);
* while (i.hasNext()) cout << i.next();
*/
``````

Of course, the problem can also be solved in `O(1)` memory (see here for a better solution).

• Your `data` is a copy of `vec2d`. If you copy all the data anyway, you might as well just copy it into a single simple `vector<int>`. Makes things easier.

``````class Vector2D {
vector<int> data;
int i = 0;
public:
Vector2D(vector<vector<int>>& vec2d) {
for (auto& v : vec2d)
data.insert(end(data), begin(v), end(v));
}

int next() {
return data[i++];
}

bool hasNext() {
return i < data.size();
}
};
``````

Java

``````public class Vector2D {

public Vector2D(List<List<Integer>> vec2d) {
for (List v : vec2d)
}

public int next() {
return data.pop();
}

public boolean hasNext() {
return !data.isEmpty();
}
}
``````

And Python :-)

``````class Vector2D:

def __init__(self, vec2d):
self.data = sum(vec2d, [])[::-1]

def next(self):
return self.data.pop()

def hasNext(self):
return bool(self.data)
``````

Though `self.data = [i for v in vec2d for i in v][::-1]` would be faster for long `vec2d`.

• Hi, Stefan. Great thanks! In fact, I have come up with this idea at the very beginning. Then I write down the following code, which however, meets Memory Limit Exceeded ...

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
int row = vec2d.size();
for (int r = 0; r < row; r++) {
int col = vec2d[r].size();
for (int c = 0; c < col; c++)
data.push_back(vec2d[r][c]);
}
idx = 0;
}

int next() {
return data[idx];
}

bool hasNext() {
return idx < data.size();
}
private:
vector<int> data;
int idx;
};
``````

Now I realize that the code has a bug in `next`, which should be `return data[idx++];`.

Well, your use of `insert` is much more concise and the Python code is just cool :-)

• Haha, yeah, I can see how that MLE can be misleading :-)

If you learn to love range-based loops, it can be nice and concise without `insert`:

``````    for (auto& v : vec2d)
for (int i : v)
data.push_back(i);
``````

• Range-based loops are just cool :-)

• Little fix: `auto&` instead of `auto` for vectors to prevent needless copies.

``for (auto& v : vec2d)``

• "since elements in vector are stored in a contiguous range of memory, the problem can be solved in O(1) memory"

I don't understand. I could similarly solve it in O(1) memory with a linked list. How does the contiguous range of memory matter?

• Hi, Stefan. Thank you for pointing out the mistake. I have updated my post.

• Hi, Stefan. Thank you. I got it :-)

• return col != -1 && (r < row && c < col);

is col != -1 needed in the hasNext() return statement?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.