251.Flatten 2D Vector

Tags: [data_structure], [list], [nested_list], [queue], [iterator]

Com: {t}

Hard: [###]

Link: https://leetcode.com/problems/flatten-2d-vector/#/description

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

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

Better Solution: Iterator

public class Vector2D implements Iterator<Integer> {
    private Iterator<List<Integer>> iter;
    private Iterator<Integer> subIter;

    public Vector2D(List<List<Integer>> vec2d) {
        if (vec2d == null || vec2d.size() == 0) {
            return;
        }
        this.iter = vec2d.iterator();
        while (this.iter.hasNext() && this.subIter == null) {
            List<Integer> subList = iter.next();
            if (subList.size() > 0) {
                this.subIter = subList.iterator();
            }
        }
    }

    @Override
    public Integer next() {
        Integer val = subIter.next();

        while (iter.hasNext() && !subIter.hasNext()) {
            List<Integer> subList = iter.next();
            if (subList.size() > 0) {
                subIter = subList.iterator();
            }
        }

        return val;
    }

    @Override
    public boolean hasNext() {
        return subIter != null && subIter.hasNext();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

Revelation:

• In Java, we should declare the type for iterator, such as Iterator<List<Integer>> iter = ....iterator();

Note:

• Time complexity = O(n), n is the total integers in the given vec2d.
• Space complexity = O(1).

Python Solution: Iterator

class Vector2D(object):

    def __init__(self, vec2d):
        """
        Initialize your data structure here.
        :type vec2d: List[List[int]]
        """
        self.main_iter = None
        self.main_next = None
        self.sub_iter = None
        self.sub_next = None

        if not vec2d:
            return

        self.main_iter = iter(vec2d)
        self.main_next = next(self.main_iter, None)

        while self.main_next is not None and not self.sub_iter:
            if len(self.main_next) > 0:
                self.sub_iter = iter(self.main_next)

            self.main_next = next(self.main_iter, None)

        if self.sub_iter:
            self.sub_next = next(self.sub_iter, None)

    def next(self):
        """
        :rtype: int
        """
        val = self.sub_next

        self.sub_next = next(self.sub_iter, None)
        if self.sub_next is None:
            while self.main_next is not None:
                if len(self.main_next) > 0:
                    self.sub_iter = iter(self.main_next)
                    break

                self.main_next = next(self.main_iter, None)

            self.main_next = next(self.main_iter, None)
            self.sub_next = next(self.sub_iter, None)

        return val

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.sub_next is not None

# Your Vector2D object will be instantiated and called as such:
# i, v = Vector2D(vec2d), []
# while i.hasNext(): v.append(i.next())

Revelation:

• In Python, iterator doesn't have 'has next' function, this is the reason why we need to maintain the 'self.main_next' and 'self.sub_next'.

Solution: Queue:

public class Vector2D implements Iterator<Integer> {
    private int index;
    private List<List<Integer>> vec2d;
    private Queue<Integer> queue;

    public Vector2D(List<List<Integer>> vec2d) {
        this.queue = new LinkedList<>();
        if (vec2d == null || vec2d.size() == 0) {
            return;
        }
        this.vec2d = vec2d;
        this.index = 0;

        while (index < vec2d.size() && queue.size() == 0) {
            List<Integer> subList = vec2d.get(index);
            if (subList.size() == 0) {
                index ++;
                continue;
            }

            for (Integer elem : subList) {
                queue.add(elem);
            }
            index ++;
        }
    }

    @Override
    public Integer next() {
        Integer val = queue.remove();
        while (index < vec2d.size() && queue.size() == 0) {
            List<Integer> subList = vec2d.get(index);
            if (subList.size() == 0) {
                index ++;
                continue;
            }

            for (Integer elem : subList) {
                queue.add(elem);
            }
            index ++;
        }

        return val;
    }

    @Override
    public boolean hasNext() {
        return queue.size() > 0;
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

Solution: Flatten At Beginning

public class Vector2D implements Iterator<Integer> {

    private List<Integer> arr;
    private int index;

    public Vector2D(List<List<Integer>> vec2d) {
        this.arr = new ArrayList<>();
        this.index = 0;

        if (vec2d == null || vec2d.size() == 0) {
            return;
        }


        for (List<Integer> subList : vec2d) {
            for (Integer elem : subList) {
                arr.add(elem);
            }
        }
    }

    @Override
    public Integer next() {
        return arr.get(index ++);
    }

    @Override
    public boolean hasNext() {
        return index < arr.size();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */