Problem Description:
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].
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 andcol.
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 alsoO(1) in an amortized sense.
The code is as follows.
1 class Vector2D { 2 public: 3 Vector2D(vector<vector<int>>& vec2d) { 4 data = vec2d; 5 r = c = 0; 6 row = vec2d.size(); 7 col = (row == 0 ? -1 : data[r].size()); 8 skipEmptyVector(); 9 } 10 11 int next() { 12 int elem = data[r][c]; 13 if (c == col - 1) { 14 r++; 15 c = 0; 16 col = data[r].size(); 17 } 18 else c++; 19 skipEmptyVector(); 20 return elem; 21 } 22 23 bool hasNext() { 24 return col != -1 && (r < row && c < col); 25 } 26 private: 27 vector<vector<int>> data; 28 int row, col, r, c; 29 void skipEmptyVector(void) { 30 while (!col) { 31 r++; 32 col = data[r].size(); 33 } 34 } 35 }; 36 37 /** 38 * Your Vector2D object will be instantiated and called as such: 39 * Vector2D i(vec2d); 40 * while (i.hasNext()) cout << i.next(); 41 */
Since we need to copy the vec2d anyway, we can just copy it into a simple vector<int>, which makes life much easier :-)
1 class Vector2D { 2 public: 3 Vector2D(vector<vector<int>>& vec2d) { 4 int row = vec2d.size(); 5 for (int r = 0; r < row; r++) { 6 int col = vec2d[r].size(); 7 for (int c = 0; c < col; c++) 8 data.push_back(vec2d[r][c]); 9 } 10 idx = 0; 11 } 12 13 int next() { 14 return data[idx++]; 15 } 16 17 bool hasNext() { 18 return idx < data.size(); 19 } 20 private: 21 vector<int> data; 22 int idx; 23 }; 24 25 /** 26 * Your Vector2D object will be instantiated and called as such: 27 * Vector2D i(vec2d); 28 * while (i.hasNext()) cout << i.next(); 29 */
Of course, since elements in vector are stored in a contiguous range of memory, the problem can be solved in O(1) memory (see here for a better solution).
