Flatten 2D Vector

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

Example:

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:

1. 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.

2. 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.

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

Solution

Using Index i, j - (72 ms, 11.78%)

class Vector2D {

private int i, j;
private int[][] v;
public Vector2D(int[][] v) {
i = 0;
j = 0;
this.v = v;
}

public int next() {
int n = 0;
if (i < v.length && j >= v[i].length) {
while (i < v.length) {
i++;
if (j < v[i].length) {
break;
}
}
}
n = v[i][j];
if (j == v[i].length - 1) {
j = 0;
i++;
} else {
j++;
}
return n;
}

public boolean hasNext() {
int ti = i;
int tj = j;
if (ti < v.length && tj < v[ti].length) {
return true;
} else if (ti < v.length) {
while (ti < v.length) {
if (tj < v[ti].length) {
return true;
}
ti++;
}
}
return false;
}
}

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

Iterator

public class Vector2D {

private Iterator<List<Integer>> i;
private Iterator<Integer> j;

public Vector2D(List<List<Integer>> vec2d) {
i = vec2d.iterator();
}

public int next() {
hasNext();
return j.next();
}

public boolean hasNext() {
while ((j == null || !j.hasNext()) && i.hasNext())
j = i.next().iterator();
return j != null && j.hasNext();
}
}

Another

public class Vector2D {
int indexList, indexEle;
List<List<Integer>> vec;

public Vector2D(List<List<Integer>> vec2d) {
indexList = 0;
indexEle = 0;
vec = vec2d;
}

public int next() {
return vec.get(indexList).get(indexEle++);
}

public boolean hasNext() {
while(indexList < vec.size()){
if(indexEle < vec.get(indexList).size())
return true;
else{
indexList++;
indexEle = 0;
}
}
return false;
}
}

Last updated