Flatten 2D Vector

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.

Implement the Vector2D class:

• Vector2D(int[][] vec) initializes the object with the 2D vector vec.
• next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all calls to next are valid.
• hasNext() returns true if there are still some elements in the vector, and false otherwise.

Constraints:
0 ≤ vec.length ≤ 200
0 ≤ vec[i].length ≤ 500
-500 ≤ vec[i][j] ≤ 500
At most 105 calls will be made to next and hasNext.

Approach 1: Flatten List in Constructor

This approach is a bad approach! We've included it to show what it looks like and to discuss why it's not ideal. This will help in designing better iterators.

In the constructor, we iterate over the 2D input vector, putting each integer into a list. Then, the problem simplifies to being a simple list iterator. We use a list rather than an array (vector) because we don’t know in advance how many integers there might be in total.

Our unpack algorithm is as follows:

• nums = a new List
• For each innerVector in the input 2D vector:
• For each number in innerVector:
• Append the number to the end of nums

We then save this list as a field of our iterator class since the next(...) and hasNext(...) methods need to access it repeatedly. By also having a position field, we can keep track of the iterator's current position.

Algorithm:
The code makes the position field point at the next element that needs to be returned by next(). Therefore, the hasNext() method simply checks if the position is a valid index of nums. An alternative approach would be to make the position point at the previous value returned, which simplifies next() but complicates hasNext().

import java.util.NoSuchElementException;

class Vector2D {
      // Constructor will put all the nums into this list.    
      private List nums = new ArrayList<>();
      // Keep track of where the Iterator is up to.
      private int position = 0;
      public Vector2D(int[][] v) {
         // We need to iterate over the 2D vector, getting all the integers
         // out of it and putting them into nums (a field).
         for (int[] innerVector : v) {
            for (int num : innerVector) {
                  nums.add(num);
            }
         }
      }

      public int next() {
         // In Java, we throw a NoSuchElementException when next() is called
         // on an exhausted Iterator.
         if (!hasNext()) throw new NoSuchElementException();
         // Store the number we need to return, as we still need to move position forward.
         int result = nums.get(position);
         // Move the position pointer forward by 1, so that it's ready for
         // the next call to next, and gives a correct hasNext result.
         position++;
         return result;
      }

      public boolean hasNext() {
         // There's nums left as long as position is a valid index of the list.
         return position < nums.size();
      }
}    
              

Complexity Analysis

Let N be the number of integers within the 2D vector, and V be the number of inner vectors.

Time Complexity:

• Constructor: O(N + V)
  In total, we append N integers to the nums list. Each append operation is O(1), giving us O(N). However, we must loop through all the inner vectors, which costs O(V). Therefore, the final time complexity is O(N + V).
• next(): O(1)
  All operations in this method, including getting an integer at a specific index of a list, are O(1).
• hasNext(): O(1)
  All operations in this method are O(1).

Space Complexity: O(N)
We create a new list that contains all the integers from the 2D vector. This is different from the time complexity; for example, in the case of [[], [2], [], [], []], we only store the integer 2. Information about the number of inner vectors is discarded.