Problem

Implement an iterator to flatten a 2d vector.

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

思路一(two iterator)

1. because the input is list of list of integer and list has an implemented iterator method, we define two iterators
   • itr1 is the type of iterator of list of integer
   • itr2 is the type of iterator of integer
2. initialize itr1 in constructor
3. go through the given example
4. if we first check if itr1 hasnext and then assign itr1.next() to itr2, then if we call hasnext multiple time , we would only got first num in each itr2.

rough idea

while itr1 hasnext()
    itr2 = itr1.next()
    if itr2 != null and itr2.hasnext()
        return true
return false

wrong, 
    because if we call hasNext() multiple times without call next(),
    elements will be skipped, because we use itr1.next()

so check itr2 first

public class Vector2D implements Iterator<Integer> {

    Iterator<List<Integer>> itr1;
    Iterator<Integer> itr2;

    public Vector2D(List<List<Integer>> vec2d) {
        if (vec2d != null && vec2d.size() != 0) {
            itr1 = vec2d.iterator();
        }
    }

    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        return itr2.next();
    }

    @Override
    public boolean hasNext() {
        /* 
            while itr2 == null or itr2 does not have next
                if !itr1 hasnext() return false
                itr2 = itr1 hasnext(), 
             repeat the above
            return true;
        */ 
        while (itr2 == null || !itr2.hasNext()) {
            if (!itr1.hasNext()) {
                return false;
            }
            itr2 = itr1.next().iterator();
        }
        return true;
    }

    @Override
    public void remove() {}
}

思路二(two pointer)

public class MyTwoPointerSolution implements Iterator<Integer>{
    private List<List<Integer>> vec2d;
    private int inO;
    private int inI;

    public MyTwoPointerSolution(List<List<Integer>> vec2d) {
        // Initialize your data structure here
        this.vec2d = vec2d;

        inO = 0;
        inI = 0;
    }

    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        Integer ans = vec2d.get(inO).get(inI);
        if (inI == vec2d.get(inO).size() - 1) {
            inO++;
            inI = 0;
        } else {
            inI++;
        }
        return ans;
    }

    @Override
    public boolean hasNext() {
        if (vec2d == null || vec2d.isEmpty()) {
            return false;
        }
        if (inO >= vec2d.size() || inI >= vec2d.get(inO).size() || vec2d.get(inO).get(inI) == null) {
            return false;
        }

        return true;
    }

    @Override
    public void remove() {}