Talentd
FleetCode
Make and follow sheets.Sign in

Flatten 2D Vector solution and explanation

MediumArrayDesignIteratorTwo Pointers4 min read50.5% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
LeetCode Q 251: Flatten 2D VectorSweet AI · 11:30 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. LeetCode Q 251: Flatten 2D VectorSweet AI · 11:30 · 1K views
  2. Leetcode 251 Flatten 2D Vector(Java版)(所有题目完整视频及代码添加小助手+VX: flageek996,网址:www.flageek996.com)FLAGeek官方频道 · 6:20 · 817 views
  3. 251. Flatten 2D VectorMuerde un zombie · 4:58 · 684 views
  4. Leetcode 251 Flatten 2D Vector pythonFLAGeek官方频道 · 7:01 · 627 views
  5. 251. Flatten 2D Vector (Leetcode Medium)Programming Live with Larry · 7:21 · 505 views
  6. LeetCode 251 Flatten 2D Vector | OO DesignHow we live in Texas · 4:09 · 378 views
  7. Leetcode 251 Flatten 2D Vector C++FLAGeek官方频道 · 5:56 · 323 views
  8. Flatten 2D Vector (Medium), C++, LeetcodeH William Polenz · 1:00:46 · 312 views
  9. Leetcode 251. Flatten 2D Vector (iterator)LetsCode · 2:09 · 196 views
  10. Flatten 2D VectorOwen Wu · 2:16 · 81 views

The problem

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

class Vector2D:
    def __init__(self, vec: List[List[int]]):
        self.i = 0
        self.j = 0
        self.vec = vec

    def next(self) -> int:
        self.forward()
        ans = self.vec[self.i][self.j]
        self.j += 1
        return ans

    def hasNext(self) -> bool:
        self.forward()
        return self.i < len(self.vec)

    def forward(self):
        while self.i < len(self.vec) and self.j >= len(self.vec[self.i]):
            self.i += 1
            self.j = 0


# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()
class Vector2D {
    private int i;
    private int j;
    private int[][] vec;

    public Vector2D(int[][] vec) {
        this.vec = vec;
    }

    public int next() {
        forward();
        return vec[i][j++];
    }

    public boolean hasNext() {
        forward();
        return i < vec.length;
    }

    private void forward() {
        while (i < vec.length && j >= vec[i].length) {
            ++i;
            j = 0;
        }
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D obj = new Vector2D(vec);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec) {
        this->vec = move(vec);
    }

    int next() {
        forward();
        return vec[i][j++];
    }

    bool hasNext() {
        forward();
        return i < vec.size();
    }

private:
    int i = 0;
    int j = 0;
    vector<vector<int>> vec;

    void forward() {
        while (i < vec.size() && j >= vec[i].size()) {
            ++i;
            j = 0;
        }
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(vec);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
class Vector2D {
    i: number;
    j: number;
    vec: number[][];

    constructor(vec: number[][]) {
        this.i = 0;
        this.j = 0;
        this.vec = vec;
    }

    next(): number {
        this.forward();
        return this.vec[this.i][this.j++];
    }

    hasNext(): boolean {
        this.forward();
        return this.i < this.vec.length;
    }

    forward(): void {
        while (this.i < this.vec.length && this.j >= this.vec[this.i].length) {
            ++this.i;
            this.j = 0;
        }
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * var obj = new Vector2D(vec)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */
type Vector2D struct {
	i, j int
	vec  [][]int
}

func Constructor(vec [][]int) Vector2D {
	return Vector2D{vec: vec}
}

func (this *Vector2D) Next() int {
	this.forward()
	ans := this.vec[this.i][this.j]
	this.j++
	return ans
}

func (this *Vector2D) HasNext() bool {
	this.forward()
	return this.i < len(this.vec)
}

func (this *Vector2D) forward() {
	for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) {
		this.i++
		this.j = 0
	}
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * obj := Constructor(vec);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */
Try this approach in the editor

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

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.

Comments

Now write it yourselfClose this page and solve Flatten 2D Vector in the editor, without looking.
Practise Flatten 2D Vector