Is Flatten 2D Vector easy or hard?

Flatten 2D Vector is generally rated Medium difficulty. The logic of flattening is straightforward, but designing a clean iterator that skips empty rows and maintains correct state between next() and hasNext() requires careful handling.

Flatten 2D Vector Python/Java solution

In Python and Java, the typical implementation stores two pointers for row and column. The hasNext() method skips empty rows and checks bounds, while next() returns the current element and advances the column pointer. This approach keeps the solution O(n) time and O(1) extra space.

How to solve Flatten 2D Vector in O(n)?

Track two pointers: row index and column index. In hasNext(), advance the row pointer while the current row is empty or fully consumed. The next() method simply returns vec[row][col] and increments the column pointer. Since every element is accessed once, the overall complexity is O(n).

What is the best approach for Flatten 2D Vector?

The two‑pointer iterator approach is considered the best solution. Maintain two indices: one for the row and one for the column. The iterator advances rows when the current inner vector is exhausted and returns elements sequentially. This processes each element once with O(n) time and O(1) extra space.

Is Flatten 2D Vector asked at Google/Amazon/Meta?

Flatten 2D Vector is a common iterator design problem that appears in interviews at companies like Google, Amazon, and Meta. It tests understanding of lazy iteration, handling nested arrays, and designing clean next()/hasNext() APIs.

What data structure is used in Flatten 2D Vector?

The problem primarily uses arrays (or lists) combined with an iterator design pattern. The optimal solution maintains two indices to traverse the nested array structure. Some alternative implementations also use queues or pre-flattened arrays.

What is the time complexity of Flatten 2D Vector?

The optimal iterator design runs in O(n) total time where n is the total number of elements in the 2D vector. Each element is visited exactly once during iteration. The space complexity can be O(1) if you only store row and column pointers.

Description Hints 7 Solution Video 11:30

251. Flatten 2D Vector

Medium50.5% acceptance4 companiesPremium elsewhere, free here

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 the calls to next are valid.
hasNext() returns true if there are still some elements in the vector, and false otherwise.

Example 1:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

Constraints:

0 <= vec.length <= 200
0 <= vec[i].length <= 500
-500 <= vec[i][j] <= 500
At most 10⁵ calls will be made to next and hasNext.

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

Asked at 4 companies

Twitter Zenefits Airbnb

Google

Topics

Hints open one at a time

Hint 1

How many variables do you need to keep track?

Hint 2

Two variables is all you need. Try with x and y.

Hint 3

Beware of empty rows. It could be the first few rows.

Hint 4

To write correct code, think about the invariant to maintain. What is it?

Hint 5

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?

Hint 6

Not sure? Think about how you would implement hasNext(). Which is more complex?

Hint 7

Common logic in two different places should be refactored into a common method.

11:30

Still stuck?Read the written solution, or watch a walkthrough.

Open solution