Flatten 2D Vector
Flatten 2D Vector is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (row and column pointers), runs in O(1) amortized per call time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy into a flat list) up.
Problem
Build an iterator class Vector2D over a two-dimensional array of integers. Vector2D(int[][] vec) receives the data; the rows may have different lengths, and some rows may be empty.
next() returns the next integer in row-major order (all of row 0 from left to right, then row 1, and so on) and moves past it. hasNext() returns true if at least one integer has not been returned yet, and false otherwise. Calling hasNext() never consumes a value.
Examples
Example 1
- Input
Vector2D([[7, 8], [], [9]]), next(), hasNext(), next(), next(), hasNext()- Output
7, true, 8, 9, false- Why
- The empty middle row is skipped; after 9 every value has been handed out.
Example 2
- Input
Vector2D([[], [4], [], [], [5, 6]]), hasNext(), next(), next(), hasNext(), next(), hasNext()- Output
true, 4, 5, true, 6, false- Why
- Leading and repeated empty rows contribute nothing, so the values come out as 4, 5, 6.
Constraints
0 <= vec.length <= 2000 <= vec[i].length <= 500-500 <= vec[i][j] <= 500- At most
10^5calls tonextandhasNextin total. nextis only called when another element exists.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy into a flat list) | O(N) constructor, O(1) per call | O(N) |
| Optimal (row and column pointers) | O(1) amortized per call | O(1) |
1Brute force (copy into a flat list)
O(N) constructor, O(1) per callEvery one of the N values is copied once when the object is built.O(N)The flat list duplicates all N values.In the constructor, walk every row and append each value to one list. The iterator is then just an index into that list.
- Constructor: for every row, for every value, append it to
flat. next(): returnflat[pos]and advancepos.hasNext(): returnpos < flat.size().
class Vector2D {
private final List<Integer> flat = new ArrayList<>();
private int pos = 0;
public Vector2D(int[][] vec) {
for (int[] row : vec)
for (int x : row) flat.add(x);
}
public int next() {
return flat.get(pos++);
}
public boolean hasNext() {
return pos < flat.size();
}
}class Vector2D:
def __init__(self, vec: List[List[int]]):
self.flat = []
for row in vec:
for x in row:
self.flat.append(x)
self.pos = 0
def next(self) -> int:
val = self.flat[self.pos]
self.pos += 1
return val
def hasNext(self) -> bool:
return self.pos < len(self.flat)class Vector2D {
vector<int> flat;
int pos = 0;
public:
Vector2D(vector<vector<int>>& vec) {
for (auto& row : vec)
for (int x : row) flat.push_back(x);
}
int next() {
return flat[pos++];
}
bool hasNext() {
return pos < (int)flat.size();
}
};class Vector2D {
constructor(vec) {
this.flat = [];
for (const row of vec)
for (const x of row) this.flat.push(x);
this.pos = 0;
}
next() {
return this.flat[this.pos++];
}
hasNext() {
return this.pos < this.flat.length;
}
}2Optimal (row and column pointers)
O(1) amortized per callEach row is skipped at most once over the whole life of the iterator, so the skipping work is spread across all calls.O(1)Only two integers are kept besides the reference to the input.Keep a reference to the original 2D array plus two indices: the current row and the column inside it. A helper moves the row index forward while the current row has no values left, so after it runs the pointers either sit on the next value or past the last row.
- Store
vec,row = 0,col = 0. advance(): whilerow < vec.lengthandcol == vec[row].length, setrow++andcol = 0.hasNext(): calladvance(), then returnrow < vec.length.next(): calladvance(), returnvec[row][col]and incrementcol.
class Vector2D {
private final int[][] vec;
private int row = 0, col = 0;
public Vector2D(int[][] vec) {
this.vec = vec;
}
private void advance() {
while (row < vec.length && col == vec[row].length) {
row++;
col = 0;
}
}
public int next() {
advance();
return vec[row][col++];
}
public boolean hasNext() {
advance();
return row < vec.length;
}
}class Vector2D:
def __init__(self, vec: List[List[int]]):
self.vec = vec
self.row = 0
self.col = 0
def _advance(self) -> None:
while self.row < len(self.vec) and self.col == len(self.vec[self.row]):
self.row += 1
self.col = 0
def next(self) -> int:
self._advance()
val = self.vec[self.row][self.col]
self.col += 1
return val
def hasNext(self) -> bool:
self._advance()
return self.row < len(self.vec)class Vector2D {
vector<vector<int>> vec;
int row = 0, col = 0;
void advance() {
while (row < (int)vec.size() && col == (int)vec[row].size()) {
row++;
col = 0;
}
}
public:
Vector2D(vector<vector<int>>& v) : vec(v) {}
int next() {
advance();
return vec[row][col++];
}
bool hasNext() {
advance();
return row < (int)vec.size();
}
};class Vector2D {
constructor(vec) {
this.vec = vec;
this.row = 0;
this.col = 0;
}
advance() {
while (this.row < this.vec.length && this.col === this.vec[this.row].length) {
this.row++;
this.col = 0;
}
}
next() {
this.advance();
return this.vec[this.row][this.col++];
}
hasNext() {
this.advance();
return this.row < this.vec.length;
}
}Edge cases to test
- The whole input is empty, or contains only empty rows
- Empty rows at the start, the middle and the end
- Calling
hasNextseveral times in a row must not skip anything - A single row holding every value
Hints
Hint 1
The simplest version copies every value into one flat list up front. What does that cost in memory?
Hint 2
Instead, remember a row index and a column index into the original data.
Hint 3
Before answering hasNext or next, move the row index forward past rows that are exhausted or empty.
FAQ
What is the best time complexity for Flatten 2D Vector?
Optimal (row and column pointers) runs in O(1) amortized per call time and O(1) extra space. Each row is skipped at most once over the whole life of the iterator, so the skipping work is spread across all calls.
Which pattern does Flatten 2D Vector use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Flatten 2D Vector?
Yes. Brute force (copy into a flat list) takes O(N) constructor, O(1) per call time and O(N) space. In the constructor, walk every row and append each value to one list.
Which edge cases should I test for Flatten 2D Vector?
The whole input is empty, or contains only empty rows; Empty rows at the start, the middle and the end; Calling hasNext several times in a row must not skip anything; A single row holding every value.