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

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

All Problems

All Solutions