Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/251.html

 251	Flatten 2D Vector

 Implement an iterator to flatten a 2d vector.

 For example,
 Given 2d vector
     [
      [1,2],
      [3],
      [4,5,6]
     ]


 By calling `next`-api repeatedly until `hasNext`-api returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

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

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

 @tag-design

Algorithm

Maintain two variables x and y, and initialize x and y to 0.

For the hasNext() function, check whether the current x is less than the total number of rows, and whether y is the same as the number of columns in the current row,

• If the same, it means that you want to go to the next line, then x increments by 1, y is initialized to 0
• If x is still less than the total number of rows at this time, indicating that the next value can be taken out, then in the next function, you can directly take out the row x, list the number as y, and increment y by 1

Note: special case for empty list

    [
    [1,2],
    [3],
    [4,5,6],
    [],
    [],
    []
    ]

Code

• Java
• C++
• Python

• import java.util.List;
  
  public class Flatten_2D_Vector {
  
      public class Vector2D {
          private int x; // which list
          private int y; // which index of current list
          private List<List<Integer>> list;
  
          /* constructor */
          public Vector2D(List<List<Integer>> vec2d) {
              this.x = 0;
              this.y = 0;
              this.list = vec2d;
          }
  
          /* API: next */
          public int next() {
              int result = list.get(x).get(y);
              if (y + 1 >= list.get(x).size()) {
                  y = 0;
                  x++;
              } else {
                  y++;
              }
              return result;
          }
  
          /* API: hasNext */
          public boolean hasNext() {
              if (list == null) {
                  return false;
              }
  
              /*
                 @note: special case for empty list
  
                   [
                   [1,2],
                   [3],
                   [4,5,6],
                   [],
                   [],
                   []
                   ]
               */
              while (x < list.size() && list.get(x).size() == 0) {
                  x++;
                  y = 0;
              }
              if (x >= list.size()) {
                  return false;
              }
              if (y >= list.get(x).size()) {
                  return false;
              }
              return true;
          }
      }
  }
  
  ############
  
  
  

• // OJ: https://leetcode.com/problems/flatten-2d-vector/
  // Time:
  //      Vector2D: O(N)
  //      next: O(1) amortized
  //      hasNext: O(1)
  // Space: O(1)
  class Vector2D {
      vector<vector<int>> v;
      int i = 0, j = 0;
      void move() {
          while (i < v.size() && j == v[i].size()) {
              ++i;
              j = 0;
          }
      }
  public:
      Vector2D(vector<vector<int>>& v) : v(v) {
          move();
      }
      int next() {
          int ans = v[i][j++];
          move();
          return ans;
      }
      bool hasNext() {
          return i < v.size();
      }
  };
  

• class Vector2D:
      def __init__(self, vec: List[List[int]]):
          self.flatten = []
          for item in vec:
              for e in item:
                  self.flatten.append(e)
          self.cur = -1
  
      def next(self) -> int:
          self.cur += 1
          return self.flatten[self.cur]
  
      def hasNext(self) -> bool:
          return self.cur < len(self.flatten) - 1
  
  
  # Your Vector2D object will be instantiated and called as such:
  # obj = Vector2D(vec)
  # param_1 = obj.next()
  # param_2 = obj.hasNext()
  
  ############
  
  class Vector2D(object):
  
    def __init__(self, vec2d):
      """
      Initialize your data structure here.
      :type vec2d: List[List[int]]
      """
      self.x = self.y = 0
      self.m = vec2d
  
    def next(self):
      """
      :rtype: int
      """
      self.y += 1
      return self.m[self.x][self.y - 1]
  
    def hasNext(self):
      """
      :rtype: bool
      """
      m = self.m
      while self.x < len(m) and self.y >= len(m[self.x]):
        self.x += 1
        self.y = 0
      return self.x < len(m)
  
  # Your Vector2D object will be instantiated and called as such:
  # i, v = Vector2D(vec2d), []
  # while i.hasNext(): v.append(i.next())
  
  

All Problems

All Solutions