Skip to main content
Talentd

Flatten 2D Vector - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersDesignIterator5 min readAsked at: Airbnb, Google, Twitter +1
Practice this problem

Problem Statement

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 105 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.

Approach Overview

Problem Overview: You need to design an iterator over a 2D list of integers so that elements are returned one by one in row‑major order. The iterator must support next() and hasNext() while correctly skipping empty inner lists.

Approach 1: Pre‑Flatten the Vector (O(n) time, O(n) space)

The simplest strategy is to flatten the entire 2D vector during initialization. Iterate through every row and append its elements into a single 1D array. Maintain a pointer idx that moves forward each time next() is called, while hasNext() checks whether idx < flattened.size(). This makes iteration trivial because the structure behaves like a normal array iterator. The tradeoff is memory usage: storing a full copy of all elements requires O(n) extra space.

Approach 2: Two Pointers Across Rows (O(n) time, O(1) space)

A more efficient design uses two indices: row for the outer vector and col for the current position inside that row. When hasNext() runs, advance row until a row with remaining elements is found, resetting col to zero each time a row is exhausted. Once a valid row exists, next() returns vec[row][col] and increments col. Each element is visited exactly once, giving O(n) total time while using only constant extra space. This pattern resembles an iterator design commonly seen with nested arrays and is closely related to two pointers and design interview questions.

Approach 3: Queue‑Based Iterator (O(n) time, O(n) space)

Another implementation pushes all elements into a queue during construction. Each next() pops from the front, and hasNext() checks whether the queue is empty. This works well when the interface is consumed heavily after initialization, since every operation becomes constant time. However, it duplicates the data structure in memory, leading to O(n) space overhead and unnecessary preprocessing compared to the pointer approach.

Recommended for interviews: The two‑pointer iterator is the expected solution. It avoids copying the data and demonstrates that you can design a lazy iterator that walks through nested containers. Showing the pre‑flatten idea first proves correctness quickly, but the constant‑space iterator shows stronger understanding of array traversal and iterator design patterns.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pre‑Flatten ArrayO(n)O(n)When simplicity matters and memory overhead is acceptable
Two Pointer IteratorO(n)O(1)Best general solution; avoids copying data and works directly on the input
Queue Based IteratorO(n)O(n)When iteration speed after initialization is the priority

Video Solution

LeetCode Q 251: Flatten 2D Vector • Sweet AI • 1,442 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Flatten 2D Vector with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search Tree Iterator

Next

Flatten Nested List Iterator