Leetcode

Flatten 2D Vector

Approach 1: Straightforward

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

C++

class Vector2D {
 public:
  Vector2D(vector<vector<int>>& vec) {
    for (const auto& 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;
};

JAVA

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

Python

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 = begin(v);
    iEnd = end(v);
  }

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

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

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

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