Flatten 2D Vector

Flatten 2D Vector is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given a 2D vector vec, represented as a list of lists of integers. Design an iterator that flattens the 2D vector and iterates through all the elements in row-major order (i.e., from left to right and top to bottom).

Implement the Vector2D class:

- Vector2D(int[][] vec) initializes the object with the 2D vector vec. - int next() returns the next element in the flattened vector. - boolean hasNext() returns true if there are still elements to be returned, or false otherwise.

Your implementation should support calling next() and hasNext() multiple times and in any order.

Return the appropriate values for each operation as described above.

Topics and companies

Topics: Array, Two Pointers, Design, Iterator.

Reported in interviews at Airbnb.

How to practise Flatten 2D Vector on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the total number of elements in all sub-vectors. Each element is visited exactly once. time and O(N), where N is the total number of elements in all sub-vectors. The output vector stores all elements. space.

Open Flatten 2D Vector in the code editor, or read the Flatten 2D Vector editorial for a worked solution with its approach and complexity analysis.

Where Flatten 2D Vector sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Flatten 2D Vector

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern