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.

Follow up:

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;
    }
}

results matching ""

    No results matching ""