251. Flatten 2D Vector

Approach 1: Straightforward

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Vector2D {
 public:
  Vector2D(vector<vector<int>>& vec) {
    for (const vector<int>& A : vec)
      for (const int a : A)
        this->vec.push_back(a);
  }

  int next() {
    return vec[i++];
  }

  bool hasNext() {
    return i < vec.size();
  }

 private:
  vector<int> vec;
  int i = 0;
};

class Vector2D {
  public Vector2D(int[][] vec) {
    for (int[] A : vec)
      for (final int a : A)
        this.vec.add(a);
  }

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

  public boolean hasNext() {
    return i < vec.size();
  }

  private List<Integer> vec = new ArrayList<>();
  private int i = 0;
}

class Vector2D:
  def __init__(self, vec: List[List[int]]):
    self.vec = []
    self.i = 0

    for A in vec:
      self.vec += A

  def next(self) -> int:
    ans = self.vec[self.i]
    self.i += 1
    return ans

  def hasNext(self) -> bool:
    return self.i < len(self.vec)

Approach 2: Iterator

• Time: $O(1)$
• Space: $O(1)$

C++

class Vector2D {
 public:
  Vector2D(vector<vector<int>>& v) {
    i = v.begin();
    iEnd = v.end();
  }

  int next() {
    moveIterator();
    return (*i)[j++];
  }

  bool hasNext() {
    moveIterator();
    return i != iEnd;
  }

 private:
  // (*i)[j] := the current pointed value
  vector<vector<int>>::iterator i, iEnd;
  int j = 0;

  void moveIterator() {
    while (i != iEnd && j == (*i).size())
      ++i, j = 0;
  }
};