251. Flatten 2D Vector (M)

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext.

Example:

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // return 1
iterator.next(); // return 2
iterator.next(); // return 3
iterator.hasNext(); // return true
iterator.hasNext(); // return true
iterator.next(); // return 4
iterator.hasNext(); // return false
</pre>

Notes:

Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases. Please see here for more details.
You may assume that next() call will always be valid, that is, there will be at least a next element in the 2d vector when next() is called.

Follow up:

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

我的答案：

class Vector2D {
private:
    vector<int> v_;
    int ptr = 0;
public:
    Vector2D(vector<vector<int>>& v) {
        v_.clear();
        ptr = 0;
        for (const auto& line:v) {
            // for (const auto& ele:line) {
            //     v_.push_back(ele);
            // }
            v_.insert(v_.end(), line.begin(), line.end());
        }
    }
    
    int next() {
        return v_[ptr++];
    }
    
    bool hasNext() {
        return (ptr < v_.size());
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Runtime: 64 ms, faster than 15.98% of C++ online submissions for Flatten 2D Vector.
Memory Usage: 24.1 MB, less than 29.48% of C++ online submissions for Flatten 2D Vector.

很慢，而且犯了小错误。

我写了

return v_[ptr];
++ptr;

哎，这个错误

我写了

    bool hasNext() {
        return (ptr < v_.size()-1);
    }

但实际上ptr是next的位置，所以是判断ptr < v_.size()！

官方答案说，不要创建新的数据结构，上面这个方法空间复杂度太高。
还可以参考这个答案：https://www.cnblogs.com/grandyang/p/5209621.html

上面这个答案的方法二修改

class Vector2D {
private:
    vector<vector<int>> v_;
    int ptr_row = 0;
    int ptr_col = 0;
public:
    Vector2D(vector<vector<int>>& v) {
        v_ = v;
        ptr_row = 0;
        ptr_col = 0;
    }
    
    int next() {
        hasNext();
        return v_[ptr_row][ptr_col++];
    }
    
    bool hasNext() {
        while (ptr_row < v_.size() and ptr_col == v_[ptr_row].size()) {
            ++ptr_row;
            ptr_col = 0;
        }
        return (ptr_row < v_.size());
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Runtime: 64 ms, faster than 15.98% of C++ online submissions for Flatten 2D Vector.
Memory Usage: 24.1 MB, less than 29.48% of C++ online submissions for Flatten 2D Vector.

但这种方法实际上没用iterator，也没法节约什么空间复杂度

这里有一个巨坑，就是
test case
["Vector2D","hasNext"]
[[[]],[null]]

实际上输入的row size是0，相当于两层null，而不是{{}}，whose row size = 1。
为了解决这个巨坑，也为了解决在末尾出现的空1Dvector，在hasNext里面需要一直往后走。然后出循环的标准不是ptr_row < v_.size()-1，而是ptr_row < v_.size()，为的是让ptr_row超出了范围，这样巨坑情况下，ptr_row=0 & v_.size() =0，也可以直接出去。如果用ptr_row判断，需要用ptr_row < v_.size()-1，并且在开头就特殊处理这个巨坑，写起来就很麻烦了。

上面答案的方法3直接用iterator的赋值，把reference &v的begin end给存起来了

我的默写：

class Vector2D {
private:
    vector<vector<int>>::iterator ptr_row;
    vector<int>::iterator ptr_col;
    vector<vector<int>>::iterator ptr_end;
public:
    Vector2D(vector<vector<int>>& v) {
        // cout << endl;
        ptr_row = v.begin();
        ptr_end = v.end();
        if (ptr_end > ptr_row) {
            ptr_col = ptr_row->begin();
        }
    }
    
    int next() {
        hasNext();
        int ans = *ptr_col;
        ++ptr_col;
        // cout << ans;
        return ans; // *(ptr_col++)
    }
    
    bool hasNext() {
        // cout << ptr_end-ptr_row << endl;
        while (ptr_row < ptr_end and ptr_col == ptr_row->end()) {
            ++ptr_row;
            if (ptr_row == ptr_end)
                break;
            ptr_col = ptr_row->begin();
        }
        return ptr_row < ptr_end;
    }
};

Runtime: 56 ms, faster than 77.14% of C++ online submissions for Flatten 2D Vector.
Memory Usage: 23.7 MB, less than 69.97% of C++ online submissions for Flatten 2D Vector.

这里还有一个巨坑，blog里面的答案3，ptr_col用的int表示，这样在hasNext里面就不用判断

            if (ptr_row == ptr_end)
                break;

因为不管怎么样，作为int的ptr_col=0是没问题的，而如果用iterator表示，那么如果v的结尾是[]，那么ptr_end->begin()就超heap了

只用int表示ptr_col的写法

class Vector2D {
private:
    vector<vector<int>>::iterator ptr_row;
    int ptr_col;
    vector<vector<int>>::iterator ptr_end;
public:
    Vector2D(vector<vector<int>>& v) {
        // cout << endl;
        ptr_row = v.begin();
        ptr_end = v.end();
        ptr_col = 0;
    }
    
    int next() {
        hasNext();
        int ans = (*ptr_row)[ptr_col];
        ++ptr_col;
        // cout << ans;
        return ans; // *(ptr_col++)
    }
    
    bool hasNext() {
        // cout << ptr_end-ptr_row << endl;
        while (ptr_row < ptr_end and ptr_col == ptr_row->size()) {
            ++ptr_row;
            ptr_col = 0;
        }
        return ptr_row < ptr_end;
    }
};

Runtime: 64 ms, faster than 15.98% of C++ online submissions for Flatten 2D Vector.
Memory Usage: 23.6 MB, less than 87.05% of C++ online submissions for Flatten 2D Vector.

速度没提升，但是内存用量小了

官方答案

Solution

Overview

This question should be fairly straightforward if you're familiar with what an Iterator is. If you aren't at all familiar with Iterators though, then we suggest having a go at Peeking Iterator. Additionally, the Solution Article for Peeking Iterator has a special introduction section that introduces you to what Iterators are.

Note that this question refers to something called a Vector. A Vector is simply another name for Array. To be consistent with the question, we've chosen to use the term Vector, rather than Array for this article (Sorry in advance for any confusion this causes, C++ programmers).

Approach 1: Flatten List in Constructor

Intuition

This approach is a bad approach! We've included it though, to show what it looks like, and to discuss why it's bad. This will help you to design good Iterators.

In the constructor, we can iterate over the 2D input vector, putting each integer into a List. Then, the problem simplifies to being a simple List Iterator. Note that the reason we use a List rather than an array (vector) is because we don't know in advance how many integers there might be in total.

Our unpack algorithm would be as follows.

nums = a new List
for each innerVector in the input 2D Vector:
    for each number in innerVector:
        append number to the end of nums

We'll then need to save this List as a field of our Iterator class, seeing as the next(...) and hasNext(...) methods will need to access it repeatedly. By then also having a position field, we can keep track of where the Iterator is up to.

Algorithm

The code shown here makes the position field point at the next element that needs to be returned by next. Therefore, the hasNext() method simply needs to check that position is a valid index of nums. A similar variant would be to make position point at the previous value that was returned. This would simplify the next() method, but complicate the hasNext() method.

Complexity Analysis

Let <math><semantics><annotation encoding="application/x-tex">N</annotation></semantics></math>N be the number of integers within the 2D Vector, and <math><semantics><annotation encoding="application/x-tex">V</annotation></semantics></math>V be the number of inner vectors.

Time complexity.
- Constructor: <math><semantics><annotation encoding="application/x-tex">O(N + V)</annotation></semantics></math>O(N+V).
  
  In total, we'll append <math><semantics><annotation encoding="application/x-tex">N</annotation></semantics></math>N integers to the nums list. Each of these appends is an <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1) operation. This gives us <math><semantics><annotation encoding="application/x-tex">O(N)</annotation></semantics></math>O(N).
  
  Something to be cautious of is that inner vectors don't have to contain integers. Think of a test cases such as [[], [2], [], [], []]. For this test case, <math><semantics><annotation encoding="application/x-tex">N = 1</annotation></semantics></math>N=1, because there's only one integer within it. However, the algorithm has to loop through all of the empty vectors. The cost of checking all the vectors is <math><semantics><annotation encoding="application/x-tex">O(V)</annotation></semantics></math>O(V).
  
  Therefore, we get a final time complexity of <math><semantics><annotation encoding="application/x-tex">O(N + V)</annotation></semantics></math>O(N+V).
- next(): <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1).
  
  All operations in this method, including getting the integer at a specific index of a list, are <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1).
- hasNext(): <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1).
  
  All operations in this method are <math><semantics><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1).
Space complexity : <math><semantics><annotation encoding="application/x-tex">O(N)</annotation></semantics></math>O(N).

We're making a new list that contains all of the integers from the 2D Vector. Notice that this is different from the time complexity; in the example of [[], [2], [], [], []], we only store the 2. All information about how many inner vectors there were is discarded.

Why is this implementation bad?

This code works, it runs fast here on Leetcode, it seems pretty straightforward to implement.

However, one of the main purposes of an Iterator is to minimize the use of auxiliary space. We should try to utilize the existing data structure as much as possible, only adding as much extra space as needed to keep track of the next value. In some situations, the data structure we want to iterate over is too large to even fit in memory anyway (think of file systems).

In the case of our above implementation, we might as well have just had a single function List<Integer> getFlattenedVector(int[][] v), which would return a List of integers, that could then be iterated over using the List types own standard Iterator.

As a general rule, you should be very cautious of implementing Iterators with a high time complexity in the constructor, with a very low time complexity in the next() and hasNext() methods. If the code using the Iterator only wanted to access the first couple of elements in the iterated collection, then a lot of time (and probably space) has been wasted!

As a side note, modifying the input collection in any way is bad design too. Iterators are only allowed to look at, not change, the collection they've been asked to iterate over.

Approach 2: Two Pointers

Intuition

Like we said above, Approach 1 is bad because it creates a new data structure instead of simply iterating over the given one. Instead, we should find a way to step through the integers one-by-one, keeping track of where we currently are in the 2D vector. The location of each number is represented with 2 indexes; the index of the inner vector, and the index of the integer within its inner vector. Here's an example 2D vector, with the indexes marked on it.

Diagram showing list with outer and inner indices

Suppose we are at the following position:

Diagram showing list item with it's inner and outer index

How do we find the next position? Well the current integer has another integer after it, within the same inner vector. Therefore, we can just increment inner index by 1. This gives the next position as shown below.

Diagram showing list item advanced to sibling

Now inner is at the end of the current inner vector. In order to get to the next integer we'll need to increment outer by 1, and set inner to 0 (as 0 is first index of the new vector).

Diagram showing list item advanced to first element of next inner vector

This time, it's a bit trickier, because we need to skip over empty vectors. To do that we repeatedly increment outer until we find an inner vector that is not empty (programmatically, this would be an outer where inner = 0 is valid). Once we find one, we stop and set inner to 0 (the first integer of the inner vector).

Diagram showing list item advanced past empty lists to next position

Note that when outer becomes equal to the length of the 2D vector, this means there are no more inner vectors and so there are no more numbers left.

Algorithm

In Approach 1, we used <math><semantics><annotation encoding="application/x-tex">O(N)</annotation></semantics></math>O(N) auxiliary space and <math><semantics><annotation encoding="application/x-tex">O(N + V)</annotation></semantics></math>O(N+V) time in the constructor. In this approach though, we perform the necessary work incrementally during calls to hasNext() and next(). This means that if the caller stops using the iterator before it's exhausted, we won't have done any unnecessary work.

We'll define an advanceToNext() helper method that checks if the current inner and outer values point to an integer, and if they don't, then it moves them forward until they point to an integer (in the way described above). If outer == vector.length becomes true, then the method terminates (because there's no integers left).

In order to ensure no unnecessary work is done, the constructor doesn't check whether or not vector[0][0] points to an integer. This is because there might be an arbitrary number of empty inner vectors at the start of the input vector; potentially costing up to <math><semantics><annotation encoding="application/x-tex">O(V)</annotation></semantics></math>O(V) operations to skip past.

Both hasNext() and next() start by calling advanceToNext() to ensure that inner and outer point to an integer, or that outer is at its "stop" value of outer = vector.length.

next() returns the integer at vector[inner][outer], and then increments inner by 1, so that the next call to advanceToNext() will start searching from after the integer we've just returned.

It is important to note that calling the hasNext() method will only cause the pointers to move if they don't point to an integer. Once they point to an integer, repeated calls to hasNext() will not move them further. Only next() is able to move them off a valid integer. This design ensures that the client code calling hasNext() multiple times will not have unusual side effects.