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:
-
Initialization - The constructor
__init__
initializes three instance variables:self.i
andself.j
are set to0
to point at the start of the 2D vector, andself.vec
is assigned the input 2D vector. -
next
Method - When this method is called, it first calls theforward
method to ensure theself.i
andself.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 tonext
. -
hasNext
Method - This method also starts by calling theforward
method to adjust the pointers as necessary. Then, it does a simple check to see ifself.i
is still within the bounds ofself.vec
. If it is, this means there are still elements left to iterate over, so it returnstrue
; otherwise, it returnsfalse
. -
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 awhile
loop that continues to run as long asself.i
is less than the length ofself.vec
andself.j
is greater than or equal to the length of the current sub-vectorself.vec[self.i]
. Within the loop,self.i
is incremented to move to the next sub-vector, andself.j
is reset to0
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. -
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.
-
Algorithm - The overall algorithm is a linear traversal with a direct addressing scheme, facilitated by two pointers that act as coordinates (
i
for row andj
for column). The solution's complexity is (O(1)) for bothnext
andhasNext
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a 2D vector example: [[1,2], [], [3], [4,5]]
.
-
Initialization: We instantiate our
Vector2D
class with our example 2D vector.self.vec
will be initialized to[[1,2], [], [3], [4,5]]
.self.i
andself.j
will both be initialized to0
.
-
next
Method: We call thenext
method.- Since
self.i
andself.j
are both0
,self.vec[0][0]
equals1
, which is returned. self.j
increments by1
, sonext
is prepared to returnself.vec[0][1]
on the next call.
- Since
-
next
Method: We call thenext
method again.- Now we're at
self.vec[0][1]
withself.i=0
andself.j=1
. That position has the value2
, so it returns2
. self.j
increments by1
but now points beyond the current sub-vector, soself.i
will need to increment to point to the next sub-vector on the next call tonext
orhasNext
.
- Now we're at
-
hasNext
Method: Let's callhasNext
now to see if more elements are available.- The
forward
method will be triggered and notice thatself.j
is beyond the current sub-vector atself.i=0
. self.i
increments to1
, but sinceself.vec[1]
is empty, it skips that and increments to2
.self.j
resets to0
.- Now
self.i=2
andself.j=0
, which is a valid position (self.vec[2][0]
contains3
), sohasNext
returnstrue
.
- The
-
next
Method: Now, if we callnext
again, it returns3
.- The internal state is now
self.i=2
andself.j=1
, but since the sub-vector atself.i=2
only has one element,forward
will be called on the nextnext
orhasNext
to move the pointers forward.
- The internal state is now
-
hasNext
andnext
: If we callhasNext
again, it would returntrue
, as there are still elements inself.vec[3]
.- Calling
next
would then return4
, and after that, the subsequent call tonext
would return5
. At this point, withself.i=3
andself.j=2
, all elements are exhausted, sohasNext
would returnfalse
.
- Calling
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
1# A class to implement a 2D vector iterator.
2class Vector2D:
3 def __init__(self, vec):
4 """
5 Initializes a new instance of the Vector2D class.
6
7 :param vec: A list of lists of integers to iterate over.
8 """
9 self.current_row = 0 # Initialize the row index
10 self.current_col = 0 # Initialize the column index
11 self.vector = vec # Store the 2D vector
12
13 def next(self) -> int:
14 """
15 Get the next element in the 2D vector.
16
17 :return: The next integer in the 2D vector.
18 """
19 # Ensure the indices are pointing to an existing value
20 self.advance_to_next()
21 # Retrieve the next value
22 value = self.vector[self.current_row][self.current_col]
23 # Move the column index forward
24 self.current_col += 1
25 return value
26
27 def hasNext(self) -> bool:
28 """
29 Check whether the 2D vector has more elements.
30
31 :return: True if there are more elements, False otherwise.
32 """
33 # Adjust the current indices to ensure they are pointing to a value
34 self.advance_to_next()
35 # Check if current row is within the vector bounds
36 return self.current_row < len(self.vector)
37
38 def advance_to_next(self):
39 """
40 Advance the indices to the next available element, if needed.
41 This moves to the next row if the current one is done.
42 """
43 # Loop while current row is within bounds and current column is beyond the current row bounds
44 while self.current_row < len(self.vector) and self.current_col >= len(self.vector[self.current_row]):
45 self.current_row += 1 # Go to the next row
46 self.current_col = 0 # Reset column index to start of the new row
47
48
49# Example of how to use the Vector2D class:
50# obj = Vector2D([[1, 2], [3], [4, 5, 6]])
51# while obj.hasNext():
52# param_1 = obj.next()
53# print(param_1)
54
1class Vector2D {
2 private int rowIndex; // keeps track of the current row in the 2D vector
3 private int colIndex; // keeps track of the current column in the current row
4 private int[][] vector; // stores the reference to the 2D vector
5
6 // Constructor initializes the 2D vector and the indices
7 public Vector2D(int[][] vec) {
8 this.vector = vec;
9 rowIndex = 0; // start at the first row
10 colIndex = 0; // start at the first column
11 }
12
13 // Returns the next element in the 2D vector and moves the pointer
14 public int next() {
15 // Move to a valid position if necessary
16 moveToNextValid();
17 // Return the current element and move the column index forward
18 return vector[rowIndex][colIndex++];
19 }
20
21 // Checks if there are more elements to iterate over in the 2D vector
22 public boolean hasNext() {
23 // Move to a valid position if necessary
24 moveToNextValid();
25 // Determine if we have a valid next element by comparing the current row index with the vector length
26 return rowIndex < vector.length;
27 }
28
29 // Moves the indices to the next valid position if the current one is not
30 private void moveToNextValid() {
31 // If the current row is exhausted (colIndex >= the row length), move to the next row until a valid element is found
32 while (rowIndex < vector.length && colIndex >= vector[rowIndex].length) {
33 rowIndex++; // move to the next row
34 colIndex = 0; // start at the beginning of the new row
35 }
36 }
37}
38
39/**
40 * The Vector2D class provides a way to iterate through a 2D vector (array of arrays) as if it were a flat array.
41 * The 'next' and 'hasNext' methods function similarly to those in an iterator, allowing for an iteration of elements in a 2D vector.
42 * The code snippet shows how to instantiate the Vector2D object and call its methods:
43 * Vector2D obj = new Vector2D(vec); // create a new Vector2D object
44 * int element = obj.next(); // retrieve the next element in the 2D vector
45 * boolean hasMore = obj.hasNext(); // check if more elements are available
46 */
47
1#include <vector>
2
3using std::vector;
4
5class Vector2D {
6public:
7 // Constructor which takes a nested vector as an input
8 // and moves it to the member variable 'nestedVector'.
9 Vector2D(vector<vector<int>>& vec) {
10 nestedVector = std::move(vec);
11 }
12
13 // Returns the next element in the 2D vector.
14 int next() {
15 moveToNextValid(); // Ensure that the current position is valid
16 return nestedVector[rowIndex][colIndex++]; // Return the element and move to the next
17 }
18
19 // Checks if there are any more elements left in the 2D vector.
20 bool hasNext() {
21 moveToNextValid(); // Ensure that the current position is valid
22 return rowIndex < nestedVector.size(); // Check if rows are still left
23 }
24
25private:
26 int rowIndex = 0; // Row index for the current element
27 int colIndex = 0; // Column index for the current element
28 vector<vector<int>> nestedVector; // 2D vector to be flattened
29
30 // Adjusts the row and column indices to point to the next valid element.
31 void moveToNextValid() {
32 // Continue moving to the next row if the current row is empty or
33 // if the column index is equal to the size of the current row (invalid).
34 while (rowIndex < nestedVector.size() && colIndex >= nestedVector[rowIndex].size()) {
35 ++rowIndex; // Move to the next row
36 colIndex = 0; // Reset column to the start
37 }
38 }
39};
40
41/**
42 * Your Vector2D object will be instantiated and called as such:
43 * Vector2D* obj = new Vector2D(vec);
44 * int param_1 = obj->next();
45 * bool param_2 = obj->hasNext();
46 */
47
1// Global index variables for keeping track of the current position in the 2D vector
2let currentIndexI: number = 0;
3let currentIndexJ: number = 0;
4// The 2D vector to be iterated over
5let vector: number[][];
6
7/**
8 * Initializes the global variables with a new 2D vector.
9 * @param vec The 2D vector to be used for iteration.
10 */
11function vector2DConstructor(vec: number[][]): void {
12 currentIndexI = 0;
13 currentIndexJ = 0;
14 vector = vec;
15}
16
17/**
18 * Advances to the next element in the 2D vector and returns it.
19 * @return The next element in the 2D vector.
20 */
21function next(): number {
22 forward(); // Ensure the indices are at the correct position for 'next' operation.
23 return vector[currentIndexI][currentIndexJ++]; // Return current element and increment the inner index.
24}
25
26/**
27 * Checks if there is a next element in the 2D vector.
28 * @return `true` if there is a next element, `false` otherwise.
29 */
30function hasNext(): boolean {
31 forward(); // Adjust the indices to point to the next available element, if any.
32 return currentIndexI < vector.length; // Return true if there are more elements to iterate over.
33}
34
35/**
36 * Adjusts the indices to skip empty inner arrays and point to the next available element.
37 */
38function forward(): void {
39 // Loop until a non-empty row is found or end of the vector is reached
40 while (currentIndexI < vector.length && currentIndexJ >= vector[currentIndexI].length) {
41 ++currentIndexI; // Move to the next row in the 2D vector.
42 currentIndexJ = 0; // Reset the inner index.
43 }
44}
45
46// Example usage:
47// vector2DConstructor([[1, 2], [3], [], [4, 5, 6]]);
48// while (hasNext()) {
49// console.log(next());
50// }
51
Time and Space Complexity
Time Complexity
-
__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. -
next
: This method invokesself.forward()
, which loops until it finds a non-empty list or reaches the end of the outer list. In the worst case, where there arem
empty inner lists before we find a non-empty one, andn
is the total number of inner lists, this can takeO(m)
. Afterward, returning the next element takesO(1)
. However, since each inner list element is accessed exactly once, the amortized time complexity for multiplenext
operations isO(1)
per operation. -
hasNext
: Similar tonext
, it callsself.forward()
, but only needs to determine if there is another element, which isO(1)
afterself.forward()
completes. For multiple calls, just like withnext
, the amortized time complexity forhasNext
isO(1)
per operation due to the way elements are accessed sequentially. -
forward
: Whileforward
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 isO(n)
withn
as the number of inner lists, the total number of operations thatforward
performs across all calls is bounded byO(n)
because every inner list is visited at most once. Consequently, the amortized complexity offorward
per call ofnext
orhasNext
becomesO(1)
.
Conclusively, next
and hasNext
have an amortized time complexity of O(1)
per operation.
Space Complexity
-
__init__
: Except the space taken by the input, the constructor only uses constant additional space,O(1)
, for the indices. -
next
,hasNext
, andforward
: 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 toO(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.
Which data structure is used in a depth first search?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!