How to Flatten 2D Vector in C++?

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext.

Example:

1 2 3 4 5 6 7 8 9

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);   iterator.next(); // return 1 iterator.next(); // return 2 iterator.next(); // return 3 iterator.hasNext(); // return true iterator.hasNext(); // return true iterator.next(); // return 4 iterator.hasNext(); // return false

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // return 1
iterator.next(); // return 2
iterator.next(); // return 3
iterator.hasNext(); // return true
iterator.hasNext(); // return true
iterator.next(); // return 4
iterator.hasNext(); // return false

Notes:
Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases. Please see here for more details. You may assume that next() call will always be valid, that is, there will be at least a next element in the 2d vector when next() is called.

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

• How many variables do you need to keep track?
• Two variables is all you need. Try with x and y.
• Beware of empty rows. It could be the first few rows.
• To write correct code, think about the invariant to maintain. What is it?
• 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?
• Not sure? Think about how you would implement hasNext(). Which is more complex?
• Common logic in two different places should be refactored into a common method.

To flatten a 2D vector/array to one-dimension list, we can pre-process the entire vector/array in the constructor, or we can use two pointer iterator that does this on the fly (more memory and time efficient).

Flatten 2D Vector to List (Early Binding)

We can use a process method to convert the 2D vector/array to one-dimension list. Then, we just need to have a pointer that walks until the 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
29
30
31
32
33

class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) {
        process(v);
    }
    
    int next() {
        return data[i ++];
    }
    
    bool hasNext() {
        return i < data.size();    
    }
    
private:
    vector<int> data;
    int i = 0;
    
    void process(vector<vector<int>>& v) {
        for (const auto &x: v) {
            for (const auto &y: x) {
                data.push_back(y);
            }
        }
    }
};
 
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) {
        process(v);
    }
    
    int next() {
        return data[i ++];
    }
    
    bool hasNext() {
        return i < data.size();    
    }
    
private:
    vector<int> data;
    int i = 0;
    
    void process(vector<vector<int>>& v) {
        for (const auto &x: v) {
            for (const auto &y: x) {
                data.push_back(y);
            }
        }
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Flatten 2D Vector using Two Pointer (Iterator)

We can use two pointer, one pointing the current row, and another pointing to the column. We also need to have a update function that will rewind the pointers to the next row, column zero if it is beyond the bounds.

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
29

class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) {
        data = v;
        i = 0;
        j = 0;
    }
    
    int next() {
        update();
        return data[i][j ++];
    }    
    
    bool hasNext() {
        update();
        return (i < data.size());
    }
    
    void update() {
        while ((i < data.size()) && (j >= data[i].size())) {
            i ++;
            j = 0;
        }        
    }
    
private:
    vector<vector<int>> data;
    int i, j;
};

class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) {
        data = v;
        i = 0;
        j = 0;
    }
    
    int next() {
        update();
        return data[i][j ++];
    }    
    
    bool hasNext() {
        update();
        return (i < data.size());
    }
    
    void update() {
        while ((i < data.size()) && (j >= data[i].size())) {
            i ++;
            j = 0;
        }        
    }
    
private:
    vector<vector<int>> data;
    int i, j;
};

This method does not expand the entire 2D vector all at once, thus more memory and time efficient.

Related Algorithms on Flattening Arrays

• How to Flatten Javascript Arrays?
• How to Unroll/Flatten Array Recursively using Javascript?

–EOF (The Ultimate Computing & Technology Blog) —