251. Flatten 2D Vector

Problem Description

The task is to design a special iterator for a 2D vector (i.e., an array of arrays or a list of lists in Python). The iterator should provide two operations: next and hasNext. The next operation should return the next element in the 2D vector, moving an internal pointer forward by one position. The hasNext operation should check if there are more elements to be traversed in the 2D vector.

The Vector2D class is initialized with a 2D vector. It maintains internal pointers (indices) to keep track of the current position within the 2D structure. For example, if the input 2D vector is [[1,2], [3], [4,5,6]], the next method should return elements in the order 1, 2, 3, 4, 5, and 6.

It is important to notice that the 2D vector may contain empty sub-vectors, and the iterator should correctly handle this case by skipping them.

Intuition

The challenge in designing this iterator lies in dealing with the 2-dimensional structure of the input, as we need to iterate over elements in a row-by-row fashion. If we reach the end of a sub-vector (or if it's empty), we need to move to the next sub-vector to continue iterating.

A straightforward intuitive approach is to maintain two pointers (indices): one for the current sub-vector we're in (let's call it i) and one for the current element within that sub-vector (j). Using these pointers, the next operation retrieves the current element and advances j. If j exceeds the bounds of the current sub-vector, we increment i and reset j to zero, effectively moving to the next sub-vector.

For the hasNext operation, we need to check whether there are any more elements left. However, just checking if i and j are within bounds is not sufficient, as there may be empty sub-vectors ahead. We perform the same action as in next to skip empty sub-vectors and move i and j to the next available element, if any. Only then do we check if i is within bounds of the 2D vector. If it is, there are still elements left to iterate over, so it returns true. Otherwise, it returns false.

The forward helper function encapsulates this logic of skipping over empty sub-vectors and advancing the internal pointers to the next available element or the end of the vector. This helper is used in both next and hasNext to avoid code duplication and ensure that the traversal logic is consistent between those two operations.

Learn more about Two Pointers patterns.

Solution Approach

The Vector2D class is implemented with the following components:

1. Initialization - The constructor __init__ initializes three instance variables: self.i and self.j are set to 0 to point at the start of the 2D vector, and self.vec is assigned the input 2D vector.

2. next Method - When this method is called, it first calls the forward method to ensure the self.i and self.j pointers are at a valid position. If the pointers point to an empty sub-vector or are out of bounds, forward will adjust them to the next available element. After this adjustment, self.vec[self.i][self.j] is guaranteed to reference a valid element, which is then returned. Afterwards, self.j is incremented to move to the next element, preparing for the next call to next.

3. hasNext Method - This method also starts by calling the forward method to adjust the pointers as necessary. Then, it does a simple check to see if self.i is still within the bounds of self.vec. If it is, this means there are still elements left to iterate over, so it returns true; otherwise, it returns false.

4. forward Method - This helper method is crucial for ensuring that the pointers skip over any empty sub-vectors and point to the next available element. The method uses a while loop that continues to run as long as self.i is less than the length of self.vec and self.j is greater than or equal to the length of the current sub-vector self.vec[self.i]. Within the loop, self.i is incremented to move to the next sub-vector, and self.j is reset to 0 to start at the beginning of the new sub-vector. This process repeats until a non-empty sub-vector is found or the end of the 2D vector is reached.

5. Data Structures - The primary data structure used in the solution is the input 2D vector itself, which is a list of lists. There are no additional data structures needed because the design intent is to iterate in-place without flattening the 2D vector into a 1D list, which would require extra space.

6. Algorithm - The overall algorithm is a linear traversal with a direct addressing scheme, facilitated by two pointers that act as coordinates (i for row and j for column). The solution's complexity is (O(1)) for both next and hasNext operations in the amortized sense, as each element and sub-vector are accessed a constant number of times across all calls.

By combining these components, the Vector2D class delivers an efficient and intuitive way to iterate over a 2D vector with varying-length sub-vectors and potentially empty sub-vectors, avoiding unnecessary space complexity and adhering to the iterator design pattern.

Example Walkthrough

Let's illustrate the solution approach using a 2D vector example: [[1,2], [], [3], [4,5]].

1. Initialization: We instantiate our Vector2D class with our example 2D vector.

   • self.vec will be initialized to [[1,2], [], [3], [4,5]].
   • self.i and self.j will both be initialized to 0.

2. next Method: We call the next method.

   • Since self.i and self.j are both 0, self.vec[0][0] equals 1, which is returned.
   • self.j increments by 1, so next is prepared to return self.vec[0][1] on the next call.

3. next Method: We call the next method again.

   • Now we're at self.vec[0][1] with self.i=0 and self.j=1. That position has the value 2, so it returns 2.
   • self.j increments by 1 but now points beyond the current sub-vector, so self.i will need to increment to point to the next sub-vector on the next call to next or hasNext.

4. hasNext Method: Let's call hasNext now to see if more elements are available.

   • The forward method will be triggered and notice that self.j is beyond the current sub-vector at self.i=0.
   • self.i increments to 1, but since self.vec[1] is empty, it skips that and increments to 2. self.j resets to 0.
   • Now self.i=2 and self.j=0, which is a valid position (self.vec[2][0] contains 3), so hasNext returns true.

5. next Method: Now, if we call next again, it returns 3.

   • The internal state is now self.i=2 and self.j=1, but since the sub-vector at self.i=2 only has one element, forward will be called on the next next or hasNext to move the pointers forward.

6. hasNext and next: If we call hasNext again, it would return true, as there are still elements in self.vec[3].

   • Calling next would then return 4, and after that, the subsequent call to next would return 5. At this point, with self.i=3 and self.j=2, all elements are exhausted, so hasNext would return false.

Throughout this process, no additional space was used, and at no point was the 2D vector converted into a 1D array. All operations are done in-place, and while the internal pointers (self.i and self.j) constantly move forward to ensure correct iteration across both sub-vectors and individual elements within them, bypassing any empty sub-vectors.

Solution Implementation

Time and Space Complexity

Time Complexity

1. __init__: It takes constant time, O(1), since it only involves assigning the input list to an instance variable and initializing a couple of integers for iteration.

2. next: This method invokes self.forward(), which loops until it finds a non-empty list or reaches the end of the outer list. In the worst case, where there are m empty inner lists before we find a non-empty one, and n is the total number of inner lists, this can take O(m). Afterward, returning the next element takes O(1). However, since each inner list element is accessed exactly once, the amortized time complexity for multiple next operations is O(1) per operation.

3. hasNext: Similar to next, it calls self.forward(), but only needs to determine if there is another element, which is O(1) after self.forward() completes. For multiple calls, just like with next, the amortized time complexity for hasNext is O(1) per operation due to the way elements are accessed sequentially.

4. forward: While forward is called by the other methods and may in the worst case iterate through all the inner lists, it does so only as far as necessary to skip empty inner lists. Thus, while the worst-case complexity for a single call is O(n) with n as the number of inner lists, the total number of operations that forward performs across all calls is bounded by O(n) because every inner list is visited at most once. Consequently, the amortized complexity of forward per call of next or hasNext becomes O(1).

Conclusively, next and hasNext have an amortized time complexity of O(1) per operation.

Space Complexity

1. __init__: Except the space taken by the input, the constructor only uses constant additional space, O(1), for the indices.

2. next, hasNext, and forward: These methods do not use additional space that scales with the size of the input. They only use a constant amount of additional space for locally-scoped variables and pointers, leading to O(1) additional space complexity.

Conclusively, the overall additional space complexity of the methods in the Vector2D class is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.