Problem description:

Implement an iterator to flatten a 2d vector.

Example:

1
2
3
4
5
6
7
8
9
Input: 2d vector =
[
  [1,2],
  [3],
  [4,5,6]
]
Output: [1,2,3,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,2,3,4,5,6].

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

Solution:

Use two iterator to denote the begin and end of the row of 2D vector. Another integer variable for the current position in the vector column.

Another thing to notice is that we need to use (*cur) to get the value in the vector.

1
2
3
4
5
6
         pos
       [ |
cur ->  [1,2],
        [3],
        [4,5,6]
end -> ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d) {
        cur= vec2d.begin();
        end= vec2d.end();
    }

    int next() {
        return (*cur)[pos++];
    }

    bool hasNext() {
        while(cur != end && pos == (*cur).size()){
            cur++;
            pos= 0;
        }
        
        return cur != end; 
    }
    vector<vector<int>>::iterator cur, end;
    int pos= 0;
};

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

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/HAhXuq
https://goo.gl/cJtZ2Y