LeetCode 251 - Flatten 2D Vector

LeetCode: Flatten 2D Vector | CrazyEgg

Implement an iterator to flatten a 2d vector.

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

Hint:

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

https://segmentfault.com/a/1190000003791233
数组法
时间 O(N) 空间 O(1)
用一个数组表示每个List的迭代器，然后再记录一个变量，用来表示当前用到了第几个迭代器。

public class Vector2D {
    List<Iterator<Integer>> its;
    int curr = 0;
    public Vector2D(List<List<Integer>> vec2d) {
        this.its = new ArrayList<Iterator<Integer>>();
        for(List<Integer> l : vec2d){
            // 只将非空的迭代器加入数组
            if(l.size() > 0){
               this.its.add(l.iterator()); 
            }
        }
    }
    public int next() {
        Integer res = its.get(curr).next();
        // 如果该迭代器用完了，换到下一个
        if(!its.get(curr).hasNext()){
            curr++;
        }
        return res;
    }
    public boolean hasNext() {
        return curr < its.size() && its.get(curr).hasNext();
    }
}

X. 双迭代器法
时间 O(N) 空间 O(1)
思路
维护两个迭代器：一个是输入的List<List<Integer>>的迭代器，它负责遍历List<Integer>的迭代器。另一个则是List<Integer>的迭代器，它负责记录当前到哪一个List的迭代器了。每次next时，我们先调用一下hasNext，确保当前List的迭代器有下一个值。

public class Vector2D {

    Iterator<List<Integer>> it;
    Iterator<Integer> curr;
    
    public Vector2D(List<List<Integer>> vec2d) {
        it = vec2d.iterator();
    }

    public int next() {
        hasNext(); // if false, throw NoSuchElementException
        return curr.next();
    }

    public boolean hasNext() {
        // 当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器
        while((curr == null || !curr.hasNext()) && it.hasNext()){
            curr = it.next().iterator();
        }
        return curr != null && curr.hasNext();
    }
}

http://buttercola.blogspot.com/2015/08/leetcode-flatten-2d-vector.html
The question itself is very easy to solve. Just several corner cases need to think of:
  -- What if the 2d vector contains empty arrays, e.g. [ ], [ ], 1 2 3 ? In this case, the next() should not output anything, but the return type is int. There the hasNext() should be more complicated in which it handles this situation. 
  -- What if the 2d vector itself is empty? Again, handle it in hasNext() 

public class Vector2D {

    private Iterator<List<Integer>> outer;

    private Iterator<Integer> inner;

    public Vector2D(List<List<Integer>> vec2d) {

        outer = vec2d.iterator();

        inner = Collections.emptyIterator(); //inner = outer.iterator(); wrong: if outer is null, then exception

    }

    public int next() { // call hasNext() first

        return inner.next();

    }

    public boolean hasNext() {

        if (inner.hasNext()) {

            return true;

        }

        if (!outer.hasNext()) {

            return false;

        }

        inner = outer.next().iterator();

        while(!inner.hasNext() && outer.hasNext()) {

            inner = outer.next().iterator();

        }

        return inner.hasNext();

    }

}

https://leetcode.com/discuss/50292/7-9-lines-added-java-and-c-o-1-space
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(); } }
http://leetcode.tgic.me/flatten-2d-vector/index.html

 3     Iterator<List<Integer>> outterIter;
 4     Iterator<Integer> innerIter = Collections.emptyIterator();
 5 
 6     public Vector2D(List<List<Integer>> vec2d) {
 7         outterIter = vec2d.iterator();
 8     }
 9 
10     public int next() {
11         return innerIter.next();
12     }
14     public boolean hasNext() {
15         if(innerIter.hasNext()){
16             return true;
17         }
18         // while to skip empty collection
19         if(!outterIter.hasNext()){
20             return false;
21         }
22 
23         innerIter = outterIter.next().iterator();
24 
25         return hasNext();
26     }

https://leetcode.com/discuss/50356/my-concise-java-solution
private List<List<Integer>> vec2d; private int index1 = 0; private int index2 = 0; private int max_row = 0; public Vector2D(List<List<Integer>> vec2d) { this.vec2d = vec2d; max_row = vec2d.size(); while(index1 < max_row && vec2d.get(index1).size() == 0) { index1++; } } public int next() { return vec2d.get(index1).get(index2++); } public boolean hasNext() { if (index1 >= max_row) { return false; } if (index2 < vec2d.get(index1).size()) { return true; } while(++index1 < max_row) { if (vec2d.get(index1).size() > 0) { index2 = 0; return true; } } return false; }
https://leetcode.com/discuss/57984/simple-and-short-java-solution-with-iterator

• Put all iterator in a queue
• Keep track of the current iterator
• Check hasNext() and next() of current

https://leetcode.com/discuss/73910/java-iterator-solution-explained

I first hold the 2D List inside a Iterator of List this allows me to operate on the subsequent list once needed. I then remove the first list from the 2D List and store as row which is evaluated when next() & hasNext() are called. I then want to ensure row iterator is pointing to a none empty list so i call the getNextRow() method. next() and hashNext() are now very simple.next() returns the next element of the current list then ensures row isn't empty. hasNext()checks row isn't null and has a next value.

public class Vector2D { Iterator<List<Integer>> itrs; Iterator<Integer> row; public Vector2D(List<List<Integer>> vec2d) { if(vec2d == null || vec2d.size() == 0) return; itrs = vec2d.iterator(); row = itrs.next().iterator(); getNextRow(); } private void getNextRow(){ while(!row.hasNext() && itrs.hasNext()) row = itrs.next().iterator(); } public int next() { int next = row.next(); getNextRow(); return next; } public boolean hasNext() { return row != null && row.hasNext(); } }
http://likemyblogger.blogspot.com/2015/08/leetcode-251-flatten-2d-vector.html

    vector<vector<int>>::iterator row_it, row_end;

    vector<int>::iterator col_it;

public:

    Vector2D(vector<vector<int>>& vec2d) {

        row_it = vec2d.begin();

        row_end = vec2d.end();

        while(row_it!=row_end && row_it->empty()) row_it++;

        if(row_it!=row_end) col_it = row_it->begin();

    }

    int next() {

        int v = *col_it;

        col_it++;

        if(col_it==row_it->end()){

            row_it++;

            while(row_it!=row_end && row_it->empty()) row_it++;

            if(row_it!=row_end) col_it = row_it->begin();

        }

        return v;

    }

    bool hasNext() {

       if(row_it==row_end) return false;

       return true;

    }

X. Brute Force
https://leetcode.com/discuss/50677/concise-java-solution

    private int[] arrCounters;
    private int counter = 0;

    public Vector2D(List<List<Integer>> vec2d) {
        int cnt = 0;
        if (vec2d == null) {
            arrCounters = new int[0];
        } else {

            for (List<Integer> l : vec2d) {
                cnt += (l == null) ? 0 : l.size();
            }
            arrCounters = new int[cnt];

            cnt = 0;
            for (List<Integer> l : vec2d) {
                for (int in : l) {
                    arrCounters[cnt++] = in;
                }
            }
        }
    }

    public int next() {
        int val = Integer.MIN_VALUE;
        if (counter < arrCounters.length) {
            val = arrCounters[counter];
        }
        counter++;
        return val;
    }

    public boolean hasNext() {
        return counter < arrCounters.length;
    }

http://www.cnblogs.com/grandyang/p/5209621.html

https://xuezhashuati.blogspot.com/2017/04/lintcode-601-flatten-2d-vector.html
因为是2D的vector，所以我们只需要2个index去定位数字：
一个定位sub list的位置，一个定位在sub list下具体元素的位置。
- Not good as the input may be a linkedlist

public class Vector2D implements Iterator<Integer> {

    private int ListIndex;
    private int ElementIndex;
    private List<List<Integer>> vec;
    public Vector2D(List<List<Integer>> vec2d) {
        // Initialize your data structure here
        ListIndex = 0;
        ElementIndex = 0;
        vec = vec2d;
    }

    @Override
    public Integer next() {
        hasNext();
        return vec.get(ListIndex).get(ElementIndex++);
    }

    @Override
    public boolean hasNext() {
        while (ListIndex < vec.size()) {
            if (ElementIndex < vec.get(ListIndex).size()) {
                return true;
            }
            else {
                ListIndex++;
                ElementIndex = 0;
            }
        }
        return false;
    }

    @Override
    public void remove() {}
}

http://www.1point3acres.com/bbs/thread-199481-1-1.html
Follow up: implement remove.

airbnb面试题汇总
2D itertaor + remove()
http://massivealgorithms.blogspot.com/2015/11/buttercola-airbnb-2d-iterator-with.html
Read full article from LeetCode: Flatten 2D Vector | CrazyEgg