# Flatten 2D Vector LeetCode Solution

Difficulty Level Medium
Frequently asked in Airbnb Apple Google Twitter ZenefitsViews 170

Table of Contents

## Problem Statement

Flatten 2D Vector LeetCode Solution – 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

### Input:

[“Vector2D”, “next”, “next”, “next”, “hasNext”, “hasNext”, “next”, “hasNext”]

[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]

### Output:

[null, 1, 2, 3, true, true, 4, false]

## Explanation

1. Invariant: We will maintain the next correct index for x,y before the next call
2. hasNext is called before we call next
3. Remember we can have empty rows
4. At next, we extract x = vec2d[x,y]. If y+1 is less than the length of the current row, then set y to y+1. Otherwise, increment x to the next row. Make sure you adjust for empty rows at this point (and at initialization).
5. hasNext just needs to check the valid row number.

The idea is to keep two iterators, it1 is an Iterator<List> to iterate through the List of Lists. it2 is an Iterator which is the iterator of the List that it1 currently visiting. Whenever we call hasNext we try to find the next appropriate it2. If the current it2 hasNext then we keep using the same it2, otherwise we go down the List of Lists via it1 till we find a List that hasNext. If we reach the end (!it1.hasNext) that means we’ve exhausted all the possibilities and we return false. next() simply returns it2.next() since hasNext() guarantees that it2 hasNext.

1. Use two pointers, `x` -> index of subarray. `y` -> index of num in subarray
2. Inside `next()`, record the current number, then move pointers. (* After `next()` is called, `x` & `y` will always be pointing to its next location)
3. Move `x` to the next non-empty array, or outside of the vector if there is none

## Code for Flatten 2D Vector

### Java Program

```import java.util.NoSuchElementException;

class Vector2D {

private int[][] v;
private int row;
private int col;

public Vector2D(int[][] v) {
this.v = v;
row = 0;
col = 0;
}

public int next() {
skipEmptyRows();
if (!hasNext()) {
throw new NoSuchElementException();
}
int next = v[row][col++];
// Increment row if col reaches the end of the current row
if (col == v[row].length) {
row++;
col = 0;
}
return next;
}

public boolean hasNext() {
skipEmptyRows();
return row < v.length - 1 || (row == v.length - 1 && col < v[row].length);
}

private void skipEmptyRows() {
// Skip empty rows
while (row < v.length && v[row].length == 0) {
row++;
}
}
}```

### Python Program

```class Vector2D(object):
def skip_empty_rows_x(self):
while self.x < len(self.vec2d) and len(self.vec2d[self.x]) == 0:
self.x = self.x + 1
return

def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
self.vec2d = vec2d
self.x, self.y = 0, 0
self.skip_empty_rows_x()

def next(self):
"""
:rtype: int
"""
x = self.vec2d[self.x][self.y]
self.y = self.y+1
if self.y == len(self.vec2d[self.x]):
self.x, self.y = self.x+1, 0
self.skip_empty_rows_x()
return x

def hasNext(self):
"""
:rtype: bool
"""
if self.x >= len(self.vec2d):
return False
return True```

## Complexity Analysis for Flatten 2D Vector LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(1) as we are using constant space.

Translate »